给定一个包含 N 个整数的数组 A[],任务是计算元组 (i, j, k, l) 的数量,使得 i, j, k 和 I 是不同的整数 (1 <= i < j < k <= N) and atleast one of the following conditions is
A.sort()
C = 0
D = dict()
for i in range(N):
for j in range(i + 1, N):
D[A[i] + A[j]] = (i, j)
for i in range(N):
for j in range(i + 1, N):
S = A[i] + A[j]
if S in D and D[S] != (i, j):
C += 1
print(C)
我得到了 8,但答案是 4
输入: 数 = 5 A = 1 1 3 1 1 输出: 4 解释: 1 2 3 4 1 2 3 5 1 3 4 5 2 3 4 5
输入: N = 2 A = 5 2 输出: 0
代码的主要问题是您不断更改字典中的值,因此当您不希望 D[s] != (i, j) 条件结果为 true 时,结果为 true。
例如,采用您的第一个示例列表,并采用代码的以下部分:
for i in range(N):
for j in range(i + 1, N):
S = A[i] + A[j]
if S in D and D[S] != (i, j):
C += 1
首先 i 为 0,j 为 1。假设 A[0] = 1 且 A[1] = 1,S 将计算为 2。当您检查 S 是否在 D 中时,结果将为 true。然而,当您检查是否 D[S] != (i, j) 时,它的计算结果也会为 true。为什么?
好吧,在这部分代码中:
for i in range(N):
for j in range(i + 1, N):
D[A[i] + A[j]] = (i, j)
您最初将 D[2] 设置为 (0, 1),但后来将其设置为 (0, 3),然后设置为 (0, 4),然后设置为 (1, 3),然后设置为 (1, 4),然后最后 (3, 4)。
我建议使用哈希表,其中键是总和(正如您现在所拥有的),值是列表。这就是事情的开始:
D = {}
for i in range(N):
for j in range(i + 1, N):
S = A[i] + A[j]
if S not in D:
D[S] = []
D[S].append((i, j))
我会让你弄清楚如何写第二部分。请注意,它与您所做的非常相似。