找指定和的整数对

暴力

先写一个暴力

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

        /**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * date: 2025-12-18 08:59:01
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,m;
int a[maxn];

void init(){
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
    } 
    std::cin >> m;

}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    init();

    int ans= 0;
    // baoli 
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        for(int j = i+1;j <= n ;++j ) // j: 1->n
        {
            if( a[i] + a[j] == m)
            {
                std::cout << a[i] << " ";
                std::cout << a[j] << "\n";

            }
        }
    }

    
    
    return 0;
}

    

二分

当然可以使用二分来做

双指针

显然排序不影响结果,先排序

下面是对枚举的优化

我们需要知道所有和i配对的可以的对数.

• 如果$i$的配对$j = p(i)$ 那么,$i+1$的配对$p(i+1)$的位置,一定在$p(i)$的左边,因为单调性.
• 固定i的时候,j从n开始从右向左一次尝试
• 情况1: 如果$a[i] + a[j] > m$,那么为了和i配对,j需要向左继续移动
• 情况2: $a[i] + a[j] == m$ ,找到的对应的配对
• 情况3: $a[i] + a[j] < m$:
  • 此时所有和$i$ 配对的j 都已经尝试完了
  • j 左边的元素都不可能和i进行配对
  • 所以应该尝试下一个i,(i=i+1)

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

        /**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * date: 2025-12-18 08:59:01
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,m;
int a[maxn];

void init(){
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
    } 
    std::cin >> m;

}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    init();
    std::sort(a+1,a+1+n);

    int ans= 0;
    //双指针
    int j = n;
    for(int i = 1;i <= n ; ) // i: 1->n
    {
        if( i > j) break; 
        if( a[i] + a[j] ==m) {
            cout << a[i] << " " << a[j] << endl;
            j--;
        }
        else if( a[i] + a[j] > m){
            j--;
        }
        else if( a[i] + a[j] < m) {
            i++;
        }
    }
    
    return 0;
}

    

双指针法: 证明1

1. 算法核心思想

本题要求在 $n$ 个整数中找出所有和为 $m$ 的整数对。通过先对数组进行从小到大排序，我们可以利用序列的单调性，使用两个指针分别从数组的首尾向中间移动，从而在 $O(n \log n)$（排序）+ $O(n)$（双指针扫描）的时间复杂度内解决问题。

2. 双指针策略的正确性证明

假设排序后的数组为 $a[1], a[2], \dots, a[n]$。设置左指针 $i = 1$，右指针 $j = n$。

单调性分析

在任意时刻，我们考察 $a[i] + a[j]$ 与目标值 $m$ 的关系：

1. 若 $a[i] + a[j] = m$：

找到一组解。由于数组中每个元素唯一（或为了找不同的组合），我们需要移动指针。此时 $a[i]$ 已经找到了它唯一的匹配对象 $a[j]$，因此 $a[i]$ 不可能再与 $j$ 左侧的任何数匹配（因为左侧的数更小），同理 $a[j]$ 也无法与 $i$ 右侧的数匹配。故执行 i++, j–。

2. 若 $a[i] + a[j] > m$：

由于数组是升序的，对于当前的 $j$ 来说，它与当前最小的 $a[i]$ 相加都已经超过了 $m$，那么它与 $i$ 右侧任何更大的元素相加必然也大于 $m$。

结论：$a[j]$ 不可能作为任何合法数对的一部分。因此，必须放弃 $a[j]$，执行 j–。

3. 若 $a[i] + a[j] < m$：

同理，对于当前的 $i$ 来说，它与当前最大的 $a[j]$ 相加仍小于 $m$，那么它与 $j$ 左侧任何更小的元素相加必然也小于 $m$。

结论：$a[i]$ 不可能作为任何合法数对的一部分。因此，必须放弃 $a[i]$，执行 i++。

边界与完备性

• 不漏解：通过上述逻辑，我们每次排除的都是“绝对不可能”与当前范围内其他元素组成 $m$ 的数。
• 终止条件：当 $i \ge j$ 时，所有可能的组合都已检查完毕，循环结束。

3. 代码优化建议

在你的代码中，针对 a[i] + a[j] == m 的情况，虽然只写了 j--，但在逻辑上 i++ 也是安全的。此外，需要注意题目是否允许重复使用同一个元素（本题要求“两个数”，通常指下标不同的两个元素）。

逻辑修正

如果 a[i] + a[j] == m 且此时 $i=j$，则不应输出，因为这是同一个数加了两次。在你的代码中 i < j 的判断已经规避了这个问题。

C++

// 核心逻辑段落
while (i < j) {
    int sum = a[i] + a[j];
    if (sum == m) {
        cout << a[i] << " " << a[j] << endl;
        i++; // 找到后，i向右，j向左，寻找下一对
        j--;
    } else if (sum < m) {
        i++; // 和太小，增大左加数
    } else {
        j--; // 和太大，减小右加数
    }
}

4. 复杂度分析

• 时间复杂度：排序耗时 $O(n \log n)$，双指针扫描耗时 $O(n)$。总时间复杂度为 $O(n \log n)$，在 $n=100,000$ 的数据范围下表现优秀。
• 空间复杂度：主要取决于存储数组的空间，为 $O(n)$。

从暴力到双指针的进化：符合直觉的推导

但是我的觉得 , 这个双指针 ,本质是对暴力算法的优化,根据单调性的特征, 及时的排除不可能答案,然后 代码就会自然而然的变成这个

你的这个切入点非常深刻。“双指针”确实不是凭空产生的妙计，而是对暴力枚举（$O(n^2)$）进行逻辑剪枝后的必然结果。

如果把暴力枚举看作是在一张二维矩阵里“全地毯式搜索”，双指针就是在利用单调性“划掉不需要看的区域”。

第一步：暴力枚举的本质

在暴力代码中，外层 i 增加，内层 j 总是从 i+1 重新跑到 n。这相当于在尝试所有可能的组合。

第二步：利用单调性进行“降维打击”

当我们把数组排序后，数组具备了单调性。此时，我们观察暴力循环中的 j：

• 在暴力枚举中，如果 $a[i] + a[j] > m$，那么对于当前的 $i$ 来说，$j$ 右边所有的数（即 $a[j+1], a[j+2] \dots$）加起来肯定都大于 $m$。
• 直觉结论：这些 $j$ 右边的数根本不需要去尝试，我们可以直接结束内层循环。

第三步：关键的“心智负担”释放点

最关键的优化来自于一个观察：随着 $i$ 的增大，$a[i]$ 变大了，为了让和维持在 $m$，配套的 $a[j]$ 必须变小。

• 当 $i$ 变成 $i+1$ 时，我们不需要让 $j$ 重新从 $n$ 开始往回跑。
• 因为在上一次循环中，我们已经确定了 $a[i]$ 和比当前 $j$ 更右边的那些数结合已经“超重”了。
• 既然 $a[i+1]$ 比 $a[i]$ 还要重，那么 $a[i+1]$ 与那些更右边的数结合，只会更超重。

第四步：代码的自然演变

既然 $j$ 不需要回溯（不需要重置为 $n$），那么 $j$ 就可以在整个算法运行期间只向左走，不回头。

1. 暴力逻辑：$i$ 走 $n$ 步，$j$ 每次都要重新出发（$n \times n$）。
2. 双指针逻辑：$i$ 从左往右走，$j$ 接力上次的位置继续往左走。
3. 结果：$i$ 最多走 $n$ 步，$j$ 最多走 $n$ 步。两人加起来一共才走了 $n$ 步左右。

总结：这种证明为什么“心智负担低”？

因为它把一个“算法技巧”转化成了一个**“常识性的搜索行为”**：

“如果我已经知道这组搭档太重了，而我现在换了一个更重的新搭档(i++)，那我之前排除掉的那些重担子(j的右边)显然更不用看了。”

这种**“不回头”**的属性，就是双指针比暴力快一个数量级的根本原因。