链表算法查找总和为 10 的对

Question

您能否建议一种算法来查找链表中加起来为 10 的所有节点对。 我想出了以下内容。

算法：从第二个节点开始比较每个节点，每个节点从头节点开始直到前一个节点（在当前比较的节点之前）并报告所有此类对。

我认为这个算法应该可以工作，但是它肯定不是最有效的算法，复杂度为 O(n2)。

任何人都可以暗示一个更有效的解决方案（可能需要线性时间）。这种解决方案可以使用附加或临时节点。

Answer 1

如果它们的范围有限（例如 -100 到 100 之间），则很容易。

创建一个数组 quant[-100..100] 然后循环遍历链表，执行：

quant[value] = quant[value] + 1

然后下面的循环就可以了。

for i = -100 to 100:
    j = 10 - i
        for k = 1 to quant[i] * quant[j]
            output i, " ", j

即使它们的范围不受限制，您也可以拥有比您建议的方法更有效的方法，方法是首先对值进行排序，然后仅保留计数而不是单个值（与上述解决方案相同）。

这是通过运行两个指针来实现的，一个在列表的开头，一个在列表的末尾。当这些指针处的数字加起来为 10 时，输出它们，并将结束指针向下移动，开始指针向上移动。

当它们大于 10 时，将结束指针向下移动。当它们较小时，将起始指针向上移动。

这依赖于排序的性质。小于 10 意味着您需要使总和更高（向上移动起始指针）。大于 10 意味着您需要减少总和（结束指针向下）。由于它们在列表中不重复（由于计数），因此等于 10 意味着您移动了两个指针。

当指针互相经过时停止。

还有一个棘手的问题，那就是当指针相等且值之和为 10 时（显然，只有当值为 5 时才会发生这种情况）。

您不会根据乘积输出对的数量，而是根据值减 1 的乘积来输出。这是因为计数为 1 的值 5 实际上并不等于 10（因为只有一个 5）。

因此，对于列表：

2 3 1 3 5 7 10 -1 11

您将得到：

Index    a  b  c  d  e  f  g  h
Value   -1  1  2  3  5  7 10 11
Count    1  1  1  2  1  1  1  1

• 您将指针 p1 起始于 a，将 p2 起始于 h。由于 -1 + 11 = 10，您输出这两个数字（如上所述，您执行 N 次，其中 N 是数）。这是 (-1,11) 的一份副本。然后将 p1 移动到 b，将 p2 移动到 g。
• 1 + 10 > 10 因此将 p1 保留在 b 处，将 p2 向下移动到 f。
• <代码>1 + 7 < 10 因此将 p1 移至 c，将 p2 保留在 f 处。
• <代码>2 + 7 < 10 因此将 p1 移至 d，将 p2 保留在 f 处。
• 3 + 7 = 10，输出两份(3,7)，因为d的计数为2，移动p1< /code> 到 e，p2 到 e。
• 5 + 5 = 10 但是 p1 = p2 所以乘积是 0 乘以 0 或 0。什么也不输出，移动 p1 到 f，p2 到 d。
• 循环从 p1 > 开始结束p2。

因此，总体输出是：

(-1,11)
( 3, 7)
( 3, 7)

这是正确的。

这是一些测试代码。您会注意到我已将 7（中点）强制设置为特定值以进行测试。显然，你不会这样做。

#include <stdio.h>

#define SZSRC 30
#define SZSORTED 20
#define SUM 14

int main (void) {
    int i, s, e, prod;
    int srcData[SZSRC];
    int sortedVal[SZSORTED];
    int sortedCnt[SZSORTED];

    // Make some random data.

    srand (time (0));
    for (i = 0; i < SZSRC; i++) {
        srcData[i] = rand() % SZSORTED;
        printf ("srcData[%2d] = %5d\n", i, srcData[i]);
    }

    // Convert to value/size array.

    for (i = 0; i < SZSORTED; i++) {
        sortedVal[i] = i;
        sortedCnt[i] = 0;
    }
    for (i = 0; i < SZSRC; i++)
        sortedCnt[srcData[i]]++;

    // Force 7+7 to specific count for testing.

    sortedCnt[7] = 2;
    for (i = 0; i < SZSORTED; i++)
        if (sortedCnt[i] != 0)
            printf ("Sorted [%3d], count = %3d\n", i, sortedCnt[i]);

    // Start and end pointers.

    s = 0;
    e = SZSORTED - 1;

    // Loop until they overlap.

    while (s <= e) {
        // Equal to desired value?

        if (sortedVal[s] + sortedVal[e] == SUM) {
            // Get product (note special case at midpoint).

            prod = (s == e)
                ? (sortedCnt[s] - 1) * (sortedCnt[e] - 1)
                : sortedCnt[s] * sortedCnt[e];

            // Output the right count.

            for (i = 0; i < prod; i++)
                printf ("(%3d,%3d)\n", sortedVal[s], sortedVal[e]);

            // Move both pointers and continue.

            s++;
            e--;
            continue;
        }

        // Less than desired, move start pointer.

        if (sortedVal[s] + sortedVal[e] < SUM) {
            s++;
            continue;
        }

        // Greater than desired, move end pointer.

        e--;
    }

    return 0;
}

您会看到上面的代码都是 O(n)，因为我没有在此版本中进行排序，只是智能地使用值作为索引。

如果最小值低于零（或非常高到会浪费太多内存的程度），您可以使用 minVal 来调整索引（另一个 O(n) 扫描来查找最小值，然后只需使用 i-minVal 而不是数组索引的 i）。

而且，即使从低到高的范围对内存来说太昂贵，您也可以使用稀疏数组。您必须对其进行排序，O(n log n)，并搜索它以获取更新计数，也是 O(n log n)，但这仍然比原始 O(n²) 更好。二分搜索的复杂度为 O(n log n) 是因为单个搜索的复杂度为 O(log n)，但您必须对每个值都执行此操作。

这是测试运行的输出，它向您展示了计算的各个阶段。

<代码>

srcData[ 0] =    13
srcData[ 1] =    16
srcData[ 2] =     9
srcData[ 3] =    14
srcData[ 4] =     0
srcData[ 5] =     8
srcData[ 6] =     9
srcData[ 7] =     8
srcData[ 8] =     5
srcData[ 9] =     9
srcData[10] =    12
srcData[11] =    18
srcData[12] =     3
srcData[13] =    14
srcData[14] =     7
srcData[15] =    16
srcData[16] =    12
srcData[17] =     8
srcData[18] =    17
srcData[19] =    11
srcData[20] =    13
srcData[21] =     3
srcData[22] =    16
srcData[23] =     9
srcData[24] =    10
srcData[25] =     3
srcData[26] =    16
srcData[27] =     9
srcData[28] =    13
srcData[29] =     5
Sorted [  0], count =   1
Sorted [  3], count =   3
Sorted [  5], count =   2
Sorted [  7], count =   2
Sorted [  8], count =   3
Sorted [  9], count =   5
Sorted [ 10], count =   1
Sorted [ 11], count =   1
Sorted [ 12], count =   2
Sorted [ 13], count =   3
Sorted [ 14], count =   2
Sorted [ 16], count =   4
Sorted [ 17], count =   1
Sorted [ 18], count =   1
(  0, 14)
(  0, 14)
(  3, 11)
(  3, 11)
(  3, 11)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  7,  7)

Answer 2

创建一个哈希集（Java 中的 HashSet）（如果您的数字有界，则可以使用稀疏数组，即您知道它们落入 +/- 100 范围内）

对于每个节点，首先检查 10-n 是否在集合中。如果是这样，您就找到了一对。无论哪种方式，然后将 n 添加到集合中并继续。

例如你有
1 - 6 - 3 - 4 - 9

1 - 9 在集合中吗？不是

6-4吗？ ？

3-7号 ？

4-6号 是的！打印 (6,4)

9 - 1？是的！打印 (9,1)

Answer 3

这是一个 NP 完全的迷你子集和问题。

Answer 4

如果您首先对集合进行排序，则会消除需要评估的数字对。