提问人：Athul Raju 提问时间：11/17/2023 最后编辑：Athul Raju 更新时间：11/17/2023 访问量：103
有人可以给出优化的方法吗？[关闭]
Can someone give an Optimized approach? [closed]
问：
求不同的三元组 （i，j，k），使得 i<j<k 和 之和可以被 d 整除？arr[i]+arr[j]+arr[k]
如果 和 它应该计数为 3arr = [3, 3, 4, 7, 8]d = 5
- 带索引的三元组 （1,2,3） 3+3+4=10
- 三元组与指数（1,3,5） 3+4+8=15
- 带指数的三元组 （2,3,4） 3+4+8=15
约束
3<=n<=10^31<=arr[i]<=10^9
def count_triplets(arr, d):
n = len(arr)
count = 0
for i in range(n - 2):
for j in range(i + 1, n - 1):
for k in range(j + 1, n):
if (arr[i] + arr[j] + arr[k]) % d == 0:
count += 1
return count
我为我的 OA 得到了这个，但只提出了 O（n^3） 方法。
答：
2赞
WizenedWizard
11/17/2023
#1
一般来说，对于这样的问题，对数组进行排序会很有帮助，这样，在每个索引上，你都可以在大量的部分上断言一些语句。考虑根据 mod d 进行排序。我的意思是数组的第一部分将构成所有数字，使得 x mod d = 0。arrxarr
因此，如果你取每个值的 d 的模数，你会得到如下结果：
[0,...,0,1,...,1,......,d-1,...,d-1]
现在您只需要找到 3 个值，总和为 0、d 或 2d。这可以在 O（n^2） 中完成。
找到三元组求和为 d 的伪代码实现，只需设置 d = 2d 并再次运行它以找到求和为 2d 的三元组。
for i in arr:
j = i + 1
k = arr.length() - 1
while (j < k):
currSum = arr[i] + arr[j] + arr[k]
if (currSum = d):
return (i, j, k)
else if (currSum > d):
k--
else j++
正如 Thierry Lathuille 和 anatoylg 所指出的，这种伪代码实现要求您遵循获取每个值的模数的过程，从而得出我上面显示的数组。此外，我们必须只检查 0、d 和 2d，因为可能的最大三重求和是 3d-3 < 3d。
评论
1赞
Thierry Lathuille
11/17/2023
if (currSum > d): ... - 你错过了一件重要的事情：我们寻找的不是等于 的总和，而是 d 的倍数。d
0赞
anatolyg
11/17/2023
幸运的是，这个问题很容易解决。首先检查数组开头是否有 3 个零。然后检查总和。然后检查总和。做。d2d
评论