洛谷：P2141：珠心算测验

Posted on 8th Nov 2025

题目

题目

分析

先要读懂题目。题目的描述有点简略，其更精确的描述是：

a+b=c+d=e的情况下，只算一次。
出现上述情况时，e可以作为加数出现，可以a+e=f。

最暴力的解法，是三重循环：前两重循环分别找两个加数，第三个循环去找是否有这个“和”存在于数组中。。如果存在，则要标记这个“和”已经出现过。这样一来，在前两重循环再次找到这个“和”的时候，就可以跳过，不重复计数。这个算法的时间复杂度是\(O(N^3)\)。

优化一下的算法是，将所有的数字排序，这样我们不用第三个循环遍历而可以用lower_bound进行两分查找。这个算法的时间复杂度是\(O(N^2 log N)\)。

最优化的算法可以达到\(O(N^2)\)的时间复杂度。下面进行详细解释。

首先，对数据进行排序，保证最大的数字在最后。也因此，保证如果存在这么一个“和”，它也一定会在数组的较后面。
其次，我们改变思路，不是找两个数字的和，而是确定一个和，然后找两个加数是不是存在。这样我们可以用一个循环控制“和”，并同时控制“和”只出现一次：一旦找到这么两个加数，就找下一个“和”。
最后，怎么找这么两个加数呢？如果还是用循环，我们还会再用到两个循环，时间复杂度再次回到\(O(N^3)\)。这种时候，用双指针是更好的。

双指针找加数

如果我们的和是第k个数，那么两个加数必然在第0-(k-1)个的范围内。用双指针法，设定：

左指针i为0，右指针j为k-1。

判定这两个位置的和：sum=numbers[i]+numbers[j]。

如果sum==numbers[k]，计数+1，终止循环，找下一个和。
如果sum<numbers[k]，说明和太小，左指针要往右（i++）。
如果sum>numbers[k]，说明和太大，右指针要往左（j--）。
以上循环，直到i<j不成立为止。

核心代码是：

for (int k = n - 1; k >= 0; k--)
{
    int target = numbers[k];
    int i = 0, j = k - 1;

    // 双指针查找两个加数
    while (i < j)
    {
        int sum = numbers[i] + numbers[j];
        if (sum == target)
        {
            count++;
            break;
        }
        else if (sum < target)
        {
            i++;  // 和太小，左指针右移
        }
        else
        {
            j--;  // 和太大，右指针左移
        }
    }
}

我们只用了两个循环，所以时间复杂度可以降到\(O(N^2)\)，是本题的最好解法。

答案

Solution

思考

最后总结一下查找两数之和的不同方式。

方式1：三重循环暴力枚举

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        for (int k = j + 1; k < n; k++)
            if (numbers[i] + numbers[j] == numbers[k])

时间复杂度：\(O(n^3)\)
优点：逻辑最直观，容易理解
缺点：最慢

方式2：枚举 + find 线性查找

for (int k = n - 1; k >= 0; k--)  // 目标和
    for (int i = 0; i < k; i++)    // 第一个加数
        int diff = target - numbers[i];
        auto it = find(numbers.begin() + i + 1, numbers.begin() + k, diff);

时间复杂度：\(O(n^3)\)
优点：代码简洁，从大到小遍历更符合直觉
缺点： find是线性查找，没有利用排序特性

方式3：枚举 + lower_bound 二分查找

for (int k = n - 1; k >= 0; k--)
    for (int i = 0; i < k; i++)
        int diff = target - numbers[i];
        auto it = lower_bound(numbers.begin() + i + 1, numbers.begin() + k, diff);

时间复杂度：\(O(n^2 log n)\)
优点：利用二分查找，比线性查找快
缺点：还不是最优

方式4：双指针（最优解）✅

for (int k = n - 1; k >= 0; k--)  // 目标和
    int i = 0, j = k - 1;
    while (i < j)
        if (numbers[i] + numbers[j] == target) // 找到
        else if (numbers[i] + numbers[j] < target) i++;
        else j--;

时间复杂度：\(O(n^2)\)
优点：最快，充分利用排序特性
原理：和太小就增大左边，和太大就减小右边

关键技巧对比

方法	查找方式	时间复杂度	适用场景
三重循环	暴力枚举	\(O(n^3)\)	数据量小，逻辑简单
`find`	线性查找	\(O(n^3)\)	代码简洁优先
`lower_bound`	二分查找	\(O(n^2 log n)\)	利用排序，中等优化
双指针	相向移动	\(O(n^2)\)	最优解，推荐

核心思想：排序后的数组，用双指针比查找更高效！

Previous Next

Table of Contents

题目

分析

双指针找加数

答案

思考