如何以 N^2 时间复杂度解决这个问题

Question

给定一个由 N 个整数组成的数组

A[]

，任务是计算元组 (i, j, k, l) 的数量，使得 i, j, k 和 I 是不同的整数 (1 <= i < j < k <= N) and at least one of the following conditions is

1. A[i] = A[j] + A[k] + A[l]

2. A[j] = A[i] + A[k] + A[l]

3. A[k] = A[i] + A[j] + A[l]

4. A[l] = A[i] + A[j] + A[k]

更正式地说，您必须找到数组中四个不同元素的组数

A[]

，其中至少一个元素等于其他三个元素的总和。

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

输入：

N = 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

Answer 1

代码的主要问题是您不断更改字典中的值，因此当您不希望 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))

我会让你弄清楚如何写第二部分。请注意，它与您所做的非常相似。