python - 查找长度为 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)