在这篇文章中，我们将描述寻找前3项在AP中，后3项在GP中的四元组个数的所有可能方法 首先，我们将解释等差数列(AP)和等比数列的基本定义(GP)。
算术级数(AP) - 它是一个数字序列，其中的公差(d)相同或恒定，这意味着两个连续数字的差异是恒定的。例如：1,3,5,7,9 | d = 2
Geometric Progression(GP) - 它是一个数字序列，其中的公比 (r) 相同，这意味着我们可以通过将前一个数字与固定数字相乘来找到每一项。例如：3, 6, 12, 24,.... | r = 2
在这个问题中，我们需要确定quadruples(a, b, c, d)N 个整数的数组 arr[ ] 有多少个索引。因此，arr[a]、arr[b] 和 arr[c] 在 AP 中，而 arr[d]、arr[c] 和 arr[b] 在 GP 中，其中所有四元组都应该是确定的。所以这是例子 -
Input : arr[ ] = { 9, 6, 4, 2, 1, 2 }
Output : 2
Explanation: Elements in the quadruples are at { 3, 2, 1, 0 } and { 5, 2, 1, 0 } indexes where quadruples are { 2, 4, 6, 9 } for both positions.
Input : arr[ ] = { 2, 6, 1, 4, 2 }
Output : 2
Explanation: Elements in the quadruples are at { 1, 3, 0, 2 } and { 1, 3, 4, 2 } indexes where quadruples are { 6, 4, 2, 1 } for both positions.现在，我们将描述两种不同的方法来找到解决方案 -
解决这个问题的一个简单的方法是使用四个嵌套循环，然后检查前三个元素是否在AP中，如果是，则检查后3个元素是否在G.P。如果是，则将 count 变量增加 1。但是，这种方法很耗时，因为它的时间复杂度为 O(n4)。
在这种方法中，我们首先找到每个数组元素的计数，然后将两个元素视为第二个和第三个数字并运行两个嵌套循环，那么第一个元素将是arr[b] – (arr[c] – arr[b ])并且第四个元素将是arr[c] * arr[c] / arr[b]。
#include <bits/stdc++.h>
using namespace std;
int main (){
unordered_map < int, int >map;
int arr[] = { 2, 6, 1, 4, 2 };
int size = sizeof (arr) / sizeof (arr[0]);
// 处理每个元素并增加计数
for (int a = 0; a < size; a++)
map[arr[a]]++;
int count = 0;
// Running two nested loops for second & third element
for (int b = 0; b < size; b++){
for (int c = 0; c < size; c++){
if (b == c)
continue;
// 减少计数
map[arr[b]]--;
map[arr[c]]--;
// 使用共同差异找到第一个元素
int first = arr[b] - (arr[c] - arr[b]);
// 使用 GP 查找第四个元素
int fourth = (arr[c] * arr[c]) / arr[b];
if ((arr[c] * arr[c]) % arr[b] == 0){
// 如果不相等则增加计数
if (arr[b] != arr[c])
count += map[first] * map[fourth];
else
count += map[first] * (map[fourth] - 1);
}
map[arr[b]]++;
map[arr[c]]++;
}
}
cout <<"四元组数： " << count;
return 0;
}输出结果四元组数： 2
在此代码中，我们使用组合数学，并为第二个和第三个元素使用两个嵌套循环，并使用arr[a] – (arr[c] – arr[b])查找第一个元素和使用arr[c] * arr[ c] / arr[b]。因此，通过保持第二个和第三个元素固定，A 和 B 索引的四元组的数量是第一个数字 * 第四个数字的计数。这里上面代码的时间复杂度是O(n2)。
在本文中，我们解决了前三项在 AP 中，后三项在 GP 中的四元组数的问题，我们讨论了使用 Bruteforce[ O(n4) ] 和 Efficient 两种方法来解决这个问题接近 [O(n2)]。
我们使用 C++ 解决了这个问题，这可以用其他各种语言（如 java、python、C 或任何其他编程语言）来解决这个问题。