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

一句话算法

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

问题模型

给定一个正整数数组 $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

C++

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;
}

Python

python

        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

        # 输出所有和恰好等于 target 的 1 下标闭区间；数组必须全为正整数。
# 正整数保证窗口和随右端点单调不减，和过大时收缩左端点不会漏解。
import sys


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [0] * (n + 1)
    for i in range(1, n + 1):
        a[i] = next(data)
    target = next(data)

    out: list[str] = []
    left = 1
    cur = 0
    for right in range(1, n + 1):
        cur += a[right]
        while left <= right and cur > target:
            cur -= a[left]
            left += 1

        if cur == target:
            out.append(f"{left} {right}")

    if out:
        sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    main()

前缀和暴力对照

C++

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;
}

Python

python

        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

        # 前缀和排序后两两配对，输出所有和等于 target 的 1 下标闭区间。
# 前缀对按 (值, 下标) 全序排序，与 C++ 比较器一致，避免不稳定排序带来的顺序歧义。
import sys


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    prefix = [(0, 0)] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = (prefix[i - 1][0] + next(data), i)
    target = next(data)

    prefix.sort()

    out: list[str] = []
    for j in range(1, n + 1):
        for i in range(j):
            if prefix[j][0] - prefix[i][0] == target:
                l = min(prefix[i][1], prefix[j][1]) + 1
                r = max(prefix[i][1], prefix[j][1])
                out.append(f"{l} {r}")

    if out:
        sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    main()

前缀和排序双指针

C++

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;
}

Python

python

        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

        # 前缀和排序后按相同值分组，双指针配对，输出所有和等于 target 的 1 下标闭区间。
# 组内元素值相同，任意两下标之差都等于 target；target == 0 时同组内两两配对。
# 组按 (值, 下标) 全序排列，输出顺序与 C++ 版严格一致。
import sys


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    prefix = [(0, 0)] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = (prefix[i - 1][0] + next(data), i)
    target = next(data)

    prefix.sort()

    groups: list[tuple[int, int]] = []
    i = 0
    while i <= n:
        j = i + 1
        while j <= n and prefix[j][0] == prefix[i][0]:
            j += 1
        groups.append((i, j))
        i = j

    out: list[str] = []
    if target == 0:
        for l, r in groups:
            for i in range(l, r):
                for j in range(i + 1, r):
                    left = min(prefix[i][1], prefix[j][1]) + 1
                    right = max(prefix[i][1], prefix[j][1])
                    out.append(f"{left} {right}")
    else:
        right_group = 0
        for left_group in range(len(groups)):
            right_group = max(right_group, left_group + 1)
            while right_group < len(groups):
                diff = (
                    prefix[groups[right_group][0]][0]
                    - prefix[groups[left_group][0]][0]
                )
                if diff >= target:
                    break
                right_group += 1
            if right_group == len(groups):
                break

            diff = (
                prefix[groups[right_group][0]][0]
                - prefix[groups[left_group][0]][0]
            )
            if diff != target:
                continue

            l1, r1 = groups[left_group]
            l2, r2 = groups[right_group]
            for i in range(l1, r1):
                for j in range(l2, r2):
                    left = min(prefix[i][1], prefix[j][1]) + 1
                    right = max(prefix[i][1], prefix[j][1])
                    out.append(f"{left} {right}")

    if out:
        sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    main()

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

最短和至少为 target 的子数组

暴力对照：

C++

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;
}

Python

python

        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

        # 求元素和 >= target 的最短连续子数组长度（前缀和暴力版）；数组必须全为正整数。
# a 用 1 下标存储；若无解输出 0。固定左端点后一旦满足即 break，因为右端点越远越长。
import sys


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + next(data)
    target = next(data)

    ans = n + 1
    for left in range(1, n + 1):
        for right in range(left, n + 1):
            if prefix[right] - prefix[left - 1] >= target:
                ans = min(ans, right - left + 1)
                break

    print(0 if ans == n + 1 else ans)


if __name__ == "__main__":
    main()

双指针优化：

C++

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;
}

Python

python

        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

        # 求元素和 >= target 的最短连续子数组长度；数组必须全为正整数。
# a 用 1 下标存储；若无解输出 0。正整数保证窗口和随右端点单调不减。
import sys


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [0] * (n + 1)
    for i in range(1, n + 1):
        a[i] = next(data)
    target = next(data)

    ans = n + 1  # n + 1 是“无解”的哨兵长度
    left = 1
    cur = 0
    for right in range(1, n + 1):
        cur += a[right]
        while left <= right and cur >= target:
            ans = min(ans, right - left + 1)
            cur -= a[left]
            left += 1

    print(0 if ans == n + 1 else ans)


if __name__ == "__main__":
    main()

测试用例

寻找和等于 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 同模型，适合练习边界写法。