我的算法书 - 双指针寻找区间和

一句话算法

正整数区间和越扩越大、越缩越小，所以可以用左右指针维护一个窗口，让每个端点只走一遍。

问题模型

给定一个正整数数组 $a_1,a_2,\dots,a_n$ 和目标值 target，常见问题有两类：

输出所有满足区间和等于 target 的连续区间。
求区间和至少为 target 的最短连续区间长度。

这里的关键条件是：数组元素都是正整数。

如果数组里有负数，右端点右移不一定让区间和变大，左端点右移也不一定让区间和变小，滑动窗口的单调性会失效。

核心直觉

窗口 [left,right] 表示当前考虑的连续区间。

因为每个数都是正的：

right 向右移动，窗口和只会变大。
left 向右移动，窗口和只会变小。

所以当窗口和太小时，只能扩右端点；当窗口和太大或已经满足条件时，可以缩左端点。两个指针都只向右走，总复杂度就是线性的。

算法步骤

输出所有和等于 target 的区间

初始化 left = 1，sum = 0。
枚举右端点 right = 1..n：
- 把 a[right] 加入 sum。
- 当 sum > target 时，不断移出 a[left] 并右移 left。
- 如果 sum == target，输出 [left,right]。

求和至少为 target 的最短区间

初始化 left = 1，sum = 0，ans = n+1。
枚举右端点 right = 1..n：
- 把 a[right] 加入 sum。
- 当 sum >= target 时：
  - 用当前长度更新答案。
  - 移出 a[left]，右移 left，尝试缩短区间。
如果答案仍为 n+1，输出 0。

算法证明

关键不变量： 对每个右端点 right，左指针只会停在仍可能产生答案的位置，不会漏掉应该检查的左端点。

以“和等于 target”为例：

如果当前 sum > target，由于数组全为正数，继续扩大右端点只会让和更大。
因此当前左端点已经不可能和当前或更大的右端点形成答案，必须右移 left。
如果 sum < target，右移 left 只会让和更小，不可能得到答案，只能扩大 right。
任意答案区间 [L,R] 在右端点走到 R 时，左端点不会提前越过 L：在越过之前，窗口和不会因为正数单调性而被迫过度收缩。

所以每个合法区间都会在它的右端点被枚举到时被发现。

“至少为 target 的最短区间”同理：当窗口已经满足条件时，只有继续收缩左端点才可能得到更短答案；当窗口不满足时，只有扩大右端点才可能重新满足。

复杂度分析

两个指针都只从左到右移动一次。

时间复杂度： $O(n)$ 。
空间复杂度： $O(1)$ 。

前缀和排序版本需要排序：

时间复杂度： $O(n\log n)$ 。
空间复杂度： $O(n)$ 。

代码实现

正整数区间和等于 target

cpp

        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

        #include <bits/stdc++.h>
using namespace std;

// Print all 1-indexed intervals whose sum is exactly target.
// The array must contain positive integers.
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long target;
    cin >> n;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> target;

    int left = 1;
    long long sum = 0;

    for (int right = 1; right <= n; ++right) {
        sum += a[right];

        while (left <= right && sum > target) {
            sum -= a[left];
            ++left;
        }

        if (sum == target) {
            cout << left << ' ' << right << '\n';
        }
    }

    return 0;
}

前缀和暴力对照

cpp

        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

        #include <bits/stdc++.h>
using namespace std;

struct Prefix {
    long long value;
    int id;

    bool operator<(const Prefix& other) const {
        if (value != other.value) return value < other.value;
        return id < other.id;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long target;
    cin >> n;

    vector<Prefix> prefix(n + 1);
    prefix[0] = {0, 0};

    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        prefix[i] = {prefix[i - 1].value + x, i};
    }
    cin >> target;

    sort(prefix.begin(), prefix.end());

    for (int j = 1; j <= n; ++j) {
        for (int i = 0; i < j; ++i) {
            if (prefix[j].value - prefix[i].value == target) {
                int l = min(prefix[i].id, prefix[j].id) + 1;
                int r = max(prefix[i].id, prefix[j].id);
                cout << l << ' ' << r << '\n';
            }
        }
    }

    return 0;
}

前缀和排序双指针

cpp

        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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

        #include <bits/stdc++.h>
using namespace std;

struct Prefix {
    long long value;
    int id;

    bool operator<(const Prefix& other) const {
        if (value != other.value) return value < other.value;
        return id < other.id;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long target;
    cin >> n;

    vector<Prefix> prefix(n + 1);
    prefix[0] = {0, 0};

    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        prefix[i] = {prefix[i - 1].value + x, i};
    }
    cin >> target;

    sort(prefix.begin(), prefix.end());

    vector<pair<int, int>> groups;
    for (int i = 0; i <= n;) {
        int j = i + 1;
        while (j <= n && prefix[j].value == prefix[i].value) ++j;
        groups.push_back({i, j});
        i = j;
    }

    if (target == 0) {
        for (auto [l, r] : groups) {
            for (int i = l; i < r; ++i) {
                for (int j = i + 1; j < r; ++j) {
                    int left = min(prefix[i].id, prefix[j].id) + 1;
                    int right = max(prefix[i].id, prefix[j].id);
                    cout << left << ' ' << right << '\n';
                }
            }
        }
        return 0;
    }

    int right_group = 0;
    for (int left_group = 0; left_group < (int)groups.size(); ++left_group) {
        right_group = max(right_group, left_group + 1);
        while (right_group < (int)groups.size()) {
            long long diff = prefix[groups[right_group].first].value
                           - prefix[groups[left_group].first].value;
            if (diff >= target) break;
            ++right_group;
        }
        if (right_group == (int)groups.size()) break;

        long long diff = prefix[groups[right_group].first].value
                       - prefix[groups[left_group].first].value;
        if (diff != target) continue;

        auto [l1, r1] = groups[left_group];
        auto [l2, r2] = groups[right_group];
        for (int i = l1; i < r1; ++i) {
            for (int j = l2; j < r2; ++j) {
                int left = min(prefix[i].id, prefix[j].id) + 1;
                int right = max(prefix[i].id, prefix[j].id);
                cout << left << ' ' << right << '\n';
            }
        }
    }

    return 0;
}

这份模板把相同前缀和值合成一组。target > 0 时在不同组之间做双指针；target == 0 时在同一组内两两配对。

最短和至少为 target 的子数组

暴力对照：

cpp

        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

        #include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long target;
    cin >> n;

    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }
    cin >> target;

    int ans = n + 1;
    for (int left = 1; left <= n; ++left) {
        for (int right = left; right <= n; ++right) {
            long long sum = prefix[right] - prefix[left - 1];
            if (sum >= target) {
                ans = min(ans, right - left + 1);
                break;
            }
        }
    }

    cout << (ans == n + 1 ? 0 : ans) << '\n';
    return 0;
}

双指针优化：

cpp

        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

        #include <bits/stdc++.h>
using namespace std;

// Minimum length of a contiguous subarray with sum >= target.
// The array must contain positive integers.
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long target;
    cin >> n;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> target;

    int ans = n + 1;
    int left = 1;
    long long sum = 0;

    for (int right = 1; right <= n; ++right) {
        sum += a[right];
        while (left <= right && sum >= target) {
            ans = min(ans, right - left + 1);
            sum -= a[left];
            ++left;
        }
    }

    cout << (ans == n + 1 ? 0 : ans) << '\n';
    return 0;
}

测试用例

寻找和等于 6 的区间：

15
6 1 2 3 4 6 4 2 8 9 10 11 12 13 14
6

输出：

寻找和至少为 7 的最短区间：

6
2 3 1 2 4 3
7

输出：

应用分类详解

区间和双指针的本质是“窗口状态对左右端点具有单调性”。

一、正整数区间和恰好为目标值

典型模式： 全是正整数，要求找连续子数组和等于某个值。 识别信号： 题面强调正整数或非负数；要求连续区间。 核心建模： 和太小扩右端点，和太大缩左端点。

应用场景	经典题目	核心思路
输出所有目标和区间	本文模型	双指针维护当前窗口和
尺取法基础题	poj-3061	正整数保证窗口单调

二、最短满足区间

典型模式： 找最短/最长连续区间，并且条件随窗口扩大单调变化。 识别信号： “最短子数组”“和至少为”“覆盖所有字符”等。 核心建模： 满足条件后尽量收缩左端点。

应用场景	经典题目	核心思路
最短和至少为 S	poj-3061	满足后缩左端点更新最短长度
最小覆盖子串	LeetCode 76	窗口满足覆盖条件后收缩

三、有负数时改用前缀和

典型模式： 数组可能含负数，窗口和不再单调。 识别信号： 数据范围允许负数，但仍然问区间和。 核心建模： 把区间和转成两个前缀和之差，再用排序、哈希表或平衡树处理。

应用场景	经典题目	核心思路
区间和等于 K	LeetCode 560	哈希表统计历史前缀和
接近目标的区间和	poj-2566	排序前缀和，双指针或邻近扫描

经典例题

poj-3061 正整数数组中求和至少为目标值的最短子数组，是滑动窗口的标准题。
poj-2566 数组允许负数，需要转成前缀和后处理。
LeetCode 209 和 POJ 3061 同模型，适合练习边界写法。