找到长度为 3 的总组合，使得总和可被给定数字和 i 整除<j<k

Question

所以，我一直在尝试寻找该问题的最佳解决方案，但我找不到小于 o(n³) 的解决方案。

问题陈述是：- 求数组中三元组的总数，使得 a[i],a[j],a[k] 之和可被给定数字 d 和 i 整除

我尝试了多种解决方案，但解决方案都达到了o(n³)。我需要一个可能小于 o(n³)

的解决方案

Answer 1

设 A 为长度为 N 的数字数组：

A = [1,2,3,4,5,6,7,8]

设 D 为除数

D = 4

可以使用额外的字典来降低复杂度 O(N^2)，从而节省您迭代每对 (a[i],a[j]) 的数组。 辅助字典将在迭代 (i,j) 对之前构建，计数为 A[k] % D = X。 因此，对于任何对 A[i]、A[j]，您可以通过从字典而不是循环中获取来判断存在多少个匹配的 A[k]。

下面是一个Python实现，演示了解决方案

T = 0 # Total possibilities
H = {} # counts all possible (A[k])%D = Key from index k

for k in range(2, len(A)):
  key = A[k]%D
  H[key] = H.get(key,0) + 1

for j in range(1, len(A)):
  if j >= 2:
    H[A[j]%D] -= 1 # when j increments it reduces options for A[k]
  for i in range(j):
    matching_val = (D - (A[i]+A[j]) % D ) % D
    to_add = H.get(matching_val, 0)
    T += to_add

print(T)

Answer 2

1. 这里的关键是考虑模运算符。列表中的每个数字

   n

   都可以表示为

   n = (x*d) + y

   ，其中

   y = n % d

   。
2. 对于任意 3 个整数

   x, y, z

   ，

   (x + y + z)

   能被

   d

   整除当且仅当

   (x%d + y%d + z%d) % d = 0

   。
3. 您可以根据余数对列表中的所有数字进行存储（即

   n%d

   ）
4. 您将拥有

   d

   个桶（范围从

   0

   到

   d-1

   ）。
5. 使用

   [0, d-1]

   范围内的整数生成所有可能的三元组，总和为

   0, d or 2*d

   。这将为您提供可用于获取有效三元组的存储桶组合。
6. 由于您知道每个桶中的元素数量，因此您可以计算有效三元组的数量。 （例如，如果

   bucket 0

   有

   10

   个元素，则三元组

   (0,0,0)

   将有

   10*9*8

   对应的三元组）。

这个算法应该足以让你走上完成问题的轨道。为读者省略了实现和其他小细节。

Answer 3

由于我无法编辑问题描述，因此我添加了带有约束的问题，以便更好地理解问题：

问题描述：

计算不同三元组

(i, j, k)

的数量，使得 0 < i < j < k ≤ n and the sum

(a[i] + a[j] + a[k])

可以被

d

整除。

示例：

a = [3, 3, 4, 7, 8]
d = 5

以下三元组可被 d = 5 整除。以下是其总和可被 d（基于 1 的索引）整除的三元组。

• 索引 (1, 2, 3)，总和 = 3 + 3 + 4 = 10
• 索引 (1, 3, 4)，总和 = 3 + 4 + 8 = 15
• 索引 (2, 3, 4)，总和 = 3 + 4 + 8 = 15

由于没有其他三元组可被

d = 5

整除，因此返回

3

。

限制：

• 3 ≤ n ≤ 10³ ，其中

  n

  是数组的长度，

  a

  。
• 1 ≤ a[i] ≤ 10⁹
• 2 ≤ d ≤ 10⁶，其中

  d

  是除数。

实施：

• 蛮力

int brute(vector<int>& nums, int d){
    int n = nums.size();
    sort(nums.begin(), nums.end());
    int pairs = 0;
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++){
            for (int k = j + 1; k < n; k++){
                if ((nums[i] + nums[j] + nums[k]) % d == 0){
                    pairs++;
                }
            }
        }
    }
    return pairs;
}

时间复杂度： O(n³)，即在最坏的情况下循环将迭代 10⁹

基于提醒的Hashmap

long long check(vector<int> lst, int d) {
    unordered_map<int, long long> buckets;

    for (int n : lst) {
        buckets[n%d]++;
    }

    long long count = 0;

    for (auto x = buckets.begin(); x != buckets.end(); ++x) {
        for (auto y = x; y != buckets.end(); ++y) {
            for (auto z = y; z != buckets.end(); ++z) {
                if ((x->first + y->first + z->first) % d == 0) {
                    if (x == y && y == z) {  
                        count += x->second * (x->second - 1) * (x->second - 2) / 6;
                    } else if (x == y && y != z) {  
                        count += x->second * (x->second - 1) / 2 * z->second;
                    } else if (x != y && y == z) {  
                        count += x->second * y->second * (y->second - 1) / 2;
                    } else {  
                        count += x->second * y->second * z->second;
                    }
                }
            }
        }
    }

    return count;
}

时间复杂度：O(n²)，最坏情况下迭代次数为 10¹²

上述代码的

C++版本

int solve(vector<int>& nums, int d){
    int n = sz(nums);
    unordered_map<int, int> counter;
    int pairs = 0;
    for (int k = 2; k < n; k++){
        int key = nums[k] % d;
        counter[key]++;
    }
    for (int j = 1; j < n; j++){
        if (j >= 2){
            counter[nums[j]%d]--;
        }
        for (int i = 0; i < j; i++){
            int match = (d - (nums[i] + nums[j]) % d) % d;
            pairs += counter.count(match) ? counter[match] : 0;
        }
    }
    return pairs;
}