Skip to content

双指针

一、基本概念🧀

1、定义🧀

Note

双指针算法，又名尺取法，是一种通过使用两个指针在数据结构中遍历来解决问题的技巧，通常能将 \(O(n^2)\) 的时间复杂度优化到 \(O(n)\)。

2、适用条件🧀

Warning

双指针算法需要满足单调性条件：假设区间 \([i,j]\) 满足条件，则对任意 \(m<i, n>j\)，\([m,n]\) 一定不满足条件。

形式化的表述较为抽象，读者可以结合例题思考双指针的适用场景和正确性。

例题🧀

e.g. 连续自然数和🧀

题目描述

对一个给定的正整数 \(M\)，求出所有的连续的正整数段（每一段至少有两个数），这些连续的自然数段中的全部数之和为 \(M\)。

例子：\(1998+1999+2000+2001+2002 = 10000\)，所以从 \(1998\) 到 \(2002\) 的一个自然数段为 \(M=10000\) 的一个解。

输入格式

包含一个整数的单独一行给出 \(M\) 的值（\(10 \le M \le 2,000,000\)）。

输出格式

每行两个正整数，给出一个满足条件的连续正整数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出行的第一个按从小到大的升序排列，对于给定的输入数据，保证至少有一个解。

输入 

1
10000

输出 

1
2
3
4
18 142 
297 328 
388 412 
1998 2002

Tip

假设 \([i,j]\) 的区间和 \(\sum_{k=i}^{j} k\) 小于 \(M\)，则 \([i+1,j]\) 的和只会更小，此时应该移动 \(j\) ,考察 \(\sum_{k=i}^{j+1} k\) 是否合法；而假设 \([i,j]\) 的区间和 \(\sum_{k=i}^{j} k\) 大于等于 \(M\)，则 \([i,j+1]\) 的和就一定大于 \(M\) ，再移动 \(j\) 无法找到有效区间，因此向右移动 \(i\) 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void solve() {
    int n;
    cin >> n;
    int sum = 3;
    for (int i = 1, j = 2; i <= (n + 1) / 2 && j <= (n + 1) / 2;) {
        while (sum < n) {
            j++;
            sum += j;
        }
        if (sum == n)
            cout << i << ' ' << j << endl;
        sum -= i;
        i++;
    }
}

e.g. 宝箱🧀

题目描述

小杨发现了 \(n\) 个宝箱，其中第 \(i\) 个宝箱的价值是 \(a_i\)。

小杨可以选择一些宝箱放入背包并带走，但是小杨的背包比较特殊，假设小杨选择的宝箱中最大价值为 \(x\)，最小价值为 \(y\)，小杨需要保证 \(x-y\leq k\)，否则小杨的背包会损坏。

小杨想知道背包不损坏的情况下，自己能够带走宝箱的总价值最大是多少。

输入格式

第一行包含两个正整数 \(n,k\)，含义如题面所示。

第二行包含 \(n\) 个正整数 \(a_1,a_2,\dots,a_n\)，代表宝箱的价值。

输出格式

输出一个整数，代表带走宝箱的最大总价值。

输入 

1
2
5 1
1 2 3 1 2

输出 

1
7

说明/提示

【样例解释】

在背包不损坏的情况下，小杨可以拿走两个价值为 \(2\) 的宝箱和一个价值为 \(3\) 的宝箱。

【数据范围】

对于全部数据，保证有 \(1\leq n\leq 1000\)，\(0\leq k\leq 1000\)，\(1\leq a_i\leq 1000\)。

Tip

与上题类似，假设 \([i,j]\) 的区间差值 \(a_j-a_i\leq k\) ，则 \([i+1,j]\) 的区间差值只会更小，所得到的答案也只会更小，此时应该记录答案并移动 \(j\) ,考察 \(a_j-a_{i+1}\) 是否合法；而假设 \([i,j]\) 的区间差值大于 \(k\) ，则 \([i,j+1]\) 及右端点更大的区间的区间差值只会更大，因此向右移动 \(i\) 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1), pre(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a.begin() + 1, a.end());
    for (int i = 1; i <= n; i++)
        pre[i] = a[i] + pre[i - 1];
    int ans = 0;
    for (int i = 1, j = 1; i <= n && j <= n;) {
        if (a[j] - a[i] <= k) {
            ans = max(ans, pre[j] - pre[i - 1]);
            j++;
        }
        else
            i++;
    }
    cout << ans << endl;
}