第七章 双指针与滑动窗口¶
本章目标：掌握双指针的三种基本模式（对撞、快慢、分离），熟练运用滑动窗口解决子串/子数组问题，理解前缀和与差分数组的区间处理技巧，并通过归并排序中的逆序对统计初步接触分治思想。
7.1 双指针概述¶
7.1.1 什么是双指针¶
双指针（Two Pointers）并不是一种单独的数据结构，而是一类通过同时维护两个（或多个）指针来高效遍历数据的技巧。其核心思想是：将暴力的 \(O(n^2)\) 或 \(O(n^3)\) 遍历，通过指针的有序移动降低为 \(O(n)\) 或 \(O(n \log n)\)。
双指针的本质
双指针的本质是利用问题的单调性或有序性，将"双重循环"优化为"单重循环 + 指针移动"。两个指针各走各的路，合起来覆盖所有需要检查的情况。
7.1.2 三种基本模式¶
graph TD
subgraph "双指针三种模式"
A["对撞指针<br/>Left ← → Right<br/>从两端向中间逼近"]
B["快慢指针<br/>Slow → → Fast → → →<br/>同向移动，速度不同"]
C["分离双指针<br/>i →<br/>j →<br/>分别在两个数组上遍历"]
end
A --> A1["有序数组上的搜索"]
B --> B1["链表环检测、中点查找"]
C --> C1["有序数组合并"]| 模式 | 指针方向 | 典型场景 | 时间复杂度 |
|---|---|---|---|
| 对撞指针 | 从两端向中间 | 有序数组两数之和、回文判断 | \(O(n)\) |
| 快慢指针 | 同向不同速 | 链表环检测、链表中点 | \(O(n)\) |
| 分离双指针 | 分别在两个数组上 | 归并排序、合并有序数组 | \(O(n + m)\) |
7.2 对撞指针经典问题¶
7.2.1 两数之和 II（LeetCode 167）¶
问题描述：给定一个升序排列的整数数组 numbers，找出两个数使得它们的和等于目标值 target。返回两个数的下标（1-indexed）。
思路分析：由于数组有序，可以利用对撞指针：
- 当
numbers[left] + numbers[right] < target时，左指针右移（增大和） - 当
numbers[left] + numbers[right] > target时，右指针左移（减小和） - 当
numbers[left] + numbers[right] == target时，找到答案
graph LR
subgraph "对撞指针过程示例 numbers=[2,7,11,15], target=9"
S1["[2,7,11,15]<br/>L=0, R=3<br/>2+15=17>9 → R--"]
S2["[2,7,11,15]<br/>L=0, R=2<br/>2+11=13>9 → R--"]
S3["[2,7,11,15]<br/>L=0, R=1<br/>2+7=9 ✅"]
S1 --> S2 --> S3
end代码实现：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size() - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return {left + 1, right + 1}; // 1-indexed
} else if (sum < target) {
left++; // 和太小，左指针右移增大
} else {
right--; // 和太大，右指针左移减小
}
}
return {}; // 无解
}
};
| 复杂度 | 值 | 说明 |
|---|---|---|
| 时间 | \(O(n)\) | 最多遍历一遍数组 |
| 空间 | \(O(1)\) | 只用了两个指针 |
7.2.2 三数之和（LeetCode 15）¶
问题描述：给定一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j != k 且 nums[i] + nums[j] + nums[k] == 0。返回所有不重复的三元组。
思路分析：先排序，然后固定第一个数 nums[i]，对剩余部分用对撞指针找两数之和为 -nums[i]。
graph TD
A["排序数组"] --> B["遍历 i = 0..n-3"]
B --> C["left = i+1, right = n-1"]
C --> D{"三数之和 == 0?"}
D -->|"< 0"| E["left++"]
D -->|"> 0"| F["right--"]
D -->|"= 0"| G["记录结果, left++, right--"]
E --> D
F --> D
G --> D代码实现：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end()); // 排序是对撞指针的前提
for (int i = 0; i < (int)nums.size() - 2; i++) {
// 剪枝：最小的数已经大于 0，后面不可能有解
if (nums[i] > 0) break;
// 去重：跳过相同的第一个数
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
left++;
} else if (sum > 0) {
right--;
} else {
res.push_back({nums[i], nums[left], nums[right]});
// 去重：跳过相同的第二个数和第三个数
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
return res;
}
};
| 复杂度 | 值 | 说明 |
|---|---|---|
| 时间 | \(O(n^2)\) | 外层遍历 \(O(n)\)，内层对撞指针 \(O(n)\) |
| 空间 | \(O(1)\) | 不计排序空间和结果空间 |
三数之和的去重
去重是本题的易错点。注意：
- 第一层去重：i > 0 && nums[i] == nums[i-1]，跳过相同的第一位
- 第二层去重：在找到答案后，left 和 right 分别跳过重复元素
- 不要在 left 和 right 移动过程中做去重，否则可能漏解
7.2.3 盛最多水的容器（LeetCode 11）¶
问题描述：给定 n 个非负整数 height[0], ..., height[n-1]，每个数代表坐标中 (i, height[i]) 处的一条垂线。找出两条线，使得它们与 x 轴构成的容器可以容纳最多的水。
思路分析：对撞指针 + 贪心。面积 = min(height[left], height[right]) * (right - left)。每次移动较短的那一边，因为移动较长的一边只会让面积更小。
graph LR
subgraph "盛水容器示意"
A["height=[1,8,6,2,5,4,8,3,7]<br/>left=0, right=8<br/>面积=min(1,7)*8=8"]
B["1 太短，left++<br/>left=1, right=8<br/>面积=min(8,7)*7=49"]
A --> B
end代码实现：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int ans = 0;
while (left < right) {
int area = min(height[left], height[right]) * (right - left);
ans = max(ans, area);
// 移动较短的那一边（贪心策略）
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return ans;
}
};
| 复杂度 | 值 | 说明 |
|---|---|---|
| 时间 | \(O(n)\) | 对撞指针各走一遍 |
| 空间 | \(O(1)\) | 常数空间 |
为什么移动短边是正确的？
如果移动长边，底边长度减 1，高度受限于短边（不会增加），面积一定更小。而移动短边虽然底边也减 1，但高度可能增加，面积有机会变大。这就是贪心的思想。
7.3 快慢指针¶
7.3.1 环形链表（LeetCode 141）¶
问题描述：给定一个链表，判断是否有环。
思路分析：快慢指针。慢指针每次走 1 步，快指针每次走 2 步。如果有环，快指针最终一定会追上慢指针。
graph LR
subgraph "快慢指针检测环"
A["1 → 2 → 3 → 4"] --> B["↑ ↓"]
B --> C["7 ← 6 ← 5"]
end
D["Slow: 1→2→3→4→5→6<br/>Fast: 1→3→5→7→2→4→6<br/>在节点6相遇 ✅"]代码实现：
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head || !head->next) return false;
ListNode *slow = head; // 慢指针：每次走 1 步
ListNode *fast = head->next; // 快指针：每次走 2 步
while (slow != fast) {
if (!fast || !fast->next) {
return false; // 快指针到达末尾，无环
}
slow = slow->next;
fast = fast->next->next;
}
return true; // 快慢指针相遇，有环
}
};
| 复杂度 | 值 | 说明 |
|---|---|---|
| 时间 | \(O(n)\) | 最多遍历链表两遍 |
| 空间 | \(O(1)\) | 只用了两个指针 |
7.3.2 环形链表 II（LeetCode 142）¶
问题描述：给定一个链表，返回链表开始入环的第一个节点。如果无环则返回 nullptr。
思路分析：先用快慢指针找到相遇点，然后从 head 和相遇点各出发一个指针，每次各走一步，再次相遇的位置就是环的入口。
graph TD
A["第一阶段：快慢指针找相遇点"] --> B["slow 走了 a+b 步"]
A --> C["fast 走了 a+b+c+b 步 = 2(a+b)"]
C --> D["推导: a = c"]
D --> E["第二阶段：从 head 和相遇点各出发一个指针"]
E --> F["各走 a 步后在环入口相遇"]代码实现：
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
// 第一阶段：快慢指针找相遇点
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
// 第二阶段：从 head 和相遇点同时出发
ListNode *ptr = head;
while (ptr != slow) {
ptr = ptr->next;
slow = slow->next;
}
return ptr; // 环的入口
}
}
return nullptr; // 无环
}
};
数学推导：为什么 a = c？
设链表头到环入口的距离为 a，环入口到相遇点的距离为 b，环的周长为 c。 - 慢指针走的距离：a + b - 快指针走的距离：a + b + c + b = a + 2b + c - 因为快指针速度是慢指针的 2 倍：2(a + b) = a + 2b + c，化简得 a = c - 所以从 head 和相遇点各走 a 步，恰好在环入口相遇。
7.3.3 链表的中间节点（LeetCode 876）¶
问题描述：给定一个头节点 head，返回链表的中间节点。如果有两个中间节点，返回第二个。
思路分析：快指针走到末尾时，慢指针恰好在中间。
graph LR
subgraph "快慢指针找中点"
S1["1→2→3→4→5<br/>Slow=1, Fast=1"]
S2["Slow=2, Fast=3"]
S3["Slow=3, Fast=5<br/>Fast到末尾，Slow即为中点"]
S1 --> S2 --> S3
end代码实现：
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next; // 慢指针走 1 步
fast = fast->next->next; // 快指针走 2 步
}
return slow; // 慢指针即为中间节点
}
};
快慢指针的应用扩展
快慢指针找中点的思想在归并排序和平衡二叉树判断中非常常用： - 归并排序分割链表：先找中点，再分别排序左右两半 - 判断平衡树：用中点作为根，递归构建平衡 BST
7.4 滑动窗口模板¶
7.4.1 什么是滑动窗口¶
滑动窗口是双指针的一种高级应用，专门用于解决子串/子数组问题。它的核心思想是维护一个"窗口" [left, right)，通过移动 right 扩大窗口和移动 left 缩小窗口，来满足题目条件。
graph LR
subgraph "滑动窗口示意"
A["[a, b, c | b, b, c, a]<br/>left=0, right=3<br/>窗口 = [a,b,c]"]
B["[a, b, c, b | b, c, a]<br/>right++ 扩大窗口"]
C["[a, b | c, b, b, c, a]<br/>left++ 缩小窗口"]
A --> B --> C
end7.4.2 固定长度滑动窗口¶
适用场景：窗口大小固定为 k 的问题。
模板代码：
#include <bits/stdc++.h>
using namespace std;
// 固定长度滑动窗口模板
// 功能：求大小为 k 的窗口的最大和
int fixedWindow(vector<int>& nums, int k) {
int n = nums.size();
int windowSum = 0;
// 第一步：初始化第一个窗口
for (int i = 0; i < k; i++) {
windowSum += nums[i];
}
int maxSum = windowSum;
// 第二步：滑动窗口
for (int i = k; i < n; i++) {
windowSum += nums[i]; // 右端进入窗口
windowSum -= nums[i - k]; // 左端离开窗口
maxSum = max(maxSum, windowSum);
}
return maxSum;
}
graph LR
subgraph "固定窗口滑动过程 k=3"
A["[1,2,3],4,5 → sum=6"]
B["1,[2,3,4],5 → sum=9"]
C["1,2,[3,4,5] → sum=12 ✅"]
A --> B --> C
end7.4.3 可变长度滑动窗口¶
适用场景：窗口大小不固定，需要根据条件动态调整。
通用模板：
#include <bits/stdc++.h>
using namespace std;
// 可变长度滑动窗口通用模板
// 求满足条件的最长/最短子数组
void variableWindow(vector<int>& nums) {
int n = nums.size();
int left = 0;
// 窗口状态：根据题目定义（如哈希表记录频次）
unordered_map<int, int> window;
for (int right = 0; right < n; right++) {
// ===== 第一步：扩大窗口 =====
// 将 nums[right] 加入窗口
window[nums[right]]++;
// ===== 第二步：判断是否需要缩小窗口 =====
while (/* 窗口需要收缩 */) {
// 将 nums[left] 移出窗口
window[nums[left]]--;
left++;
}
// ===== 第三步：更新答案 =====
// 在这里根据题目要求更新结果
}
}
graph TD
A["right 指针逐个右移"] --> B{"窗口满足条件？"}
B -->|否| A
B -->|是，但还可以优化| C["left 指针右移，缩小窗口"]
C --> B
B -->|是，记录最优解| D["更新答案"]
D --> A滑动窗口的两个关键
- right 只会右移：每个元素最多进入窗口一次
- left 只会右移：每个元素最多离开窗口一次
- 因此总时间复杂度为 \(O(n)\)，虽然有
while循环，但left和right各自最多移动 n 次
7.5 滑动窗口经典问题¶
7.5.1 无重复字符的最长子串（LeetCode 3）¶
问题描述：给定一个字符串 s，找出其中不含重复字符的最长子串的长度。
思路分析：用滑动窗口 + 哈希表记录窗口内每个字符的出现次数。当窗口内出现重复字符时，移动左边界直到重复消失。
graph LR
subgraph "过程示例 s=abcabcbb"
S1["[a]bca → len=1"]
S2["[a,b]cab → len=2"]
S3["[a,b,c]abc → len=3"]
S4["a[b,c,a]bcb → 发现重复a, left=1, len=3"]
S5["a[b,c,a,b]cb → 发现重复b, left=2, len=3"]
S6["ab[c,a,b,c]bb → 发现重复c, left=3, len=3"]
S7["abc[a,b,c,b,b] → 最终答案=3"]
S1 --> S2 --> S3 --> S4 --> S5 --> S6 --> S7
end代码实现：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> window; // 记录窗口中每个字符的频次
int left = 0;
int ans = 0;
for (int right = 0; right < (int)s.size(); right++) {
// 扩大窗口：加入右边字符
window[s[right]]++;
// 缩小窗口：当窗口中有重复字符时，移动左边界
while (window[s[right]] > 1) {
window[s[left]]--;
left++;
}
// 更新答案
ans = max(ans, right - left + 1);
}
return ans;
}
};
int main() {
Solution sol;
cout << sol.lengthOfLongestSubstring("abcabcbb") << endl; // 输出 3
cout << sol.lengthOfLongestSubstring("bbbbb") << endl; // 输出 1
cout << sol.lengthOfLongestSubstring("pwwkew") << endl; // 输出 3
return 0;
}
| 复杂度 | 值 | 说明 |
|---|---|---|
| 时间 | \(O(n)\) | left 和 right 各最多移动 n 次 |
| 空间 | \(O(\min(n, \vert\Sigma\vert))\) | 哈希表大小不超过字符集大小 |
7.5.2 最小覆盖子串（LeetCode 76）¶
问题描述：给定字符串 s 和 t，找出 s 中包含 t 所有字符的最短子串。
思路分析：滑动窗口 + 计数器。先统计 t 中每个字符的需求数量。窗口扩张时减少需求，窗口收缩时恢复需求。当所有需求都被满足时更新答案。
代码实现：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> need, window;
// 统计 t 中每个字符的需求量
for (char c : t) need[c]++;
int left = 0;
int valid = 0; // 已满足条件的字符种类数
int start = 0; // 最短子串的起始位置
int len = INT_MAX; // 最短子串的长度
for (int right = 0; right < (int)s.size(); right++) {
char c = s[right];
// ---- 扩大窗口 ----
if (need.count(c)) {
window[c]++;
if (window[c] == need[c]) {
valid++; // 该字符的数量已满足要求
}
}
// ---- 缩小窗口：当所有字符都满足条件时 ----
while (valid == (int)need.size()) {
// 更新最短子串
if (right - left + 1 < len) {
start = left;
len = right - left + 1;
}
char d = s[left];
left++;
if (need.count(d)) {
if (window[d] == need[d]) {
valid--; // 该字符不再满足条件
}
window[d]--;
}
}
}
return len == INT_MAX ? "" : s.substr(start, len);
}
};
int main() {
Solution sol;
cout << sol.minWindow("ADOBECODEBANC", "ABC") << endl; // 输出 BANC
cout << sol.minWindow("a", "a") << endl; // 输出 a
return 0;
}
| 复杂度 | 值 | 说明 |
|---|---|---|
| 时间 | \(O(n + m)\) | n 为 s 长度，m 为 t 长度 |
| 空间 | \(O(\vert\Sigma\vert)\) | 哈希表大小不超过字符集 |
滑动窗口模板的关键变量
need：目标字符串t的字符需求表window：当前窗口中的字符计数valid：已满足需求的字符种类数（不是总个数！）- 当
valid == need.size()时，说明窗口已经覆盖了t的所有字符
7.6 前缀和¶
7.6.1 一维前缀和¶
问题描述：给定数组 nums，多次询问区间 [l, r] 的元素之和。
暴力方法：每次查询遍历区间，时间 \(O(n)\) 每次。前缀和可以做到 \(O(1)\) 每次查询。
定义：prefix[i] = nums[0] + nums[1] + ... + nums[i-1]，即前 i 个元素的和（prefix[0] = 0）。
graph LR
subgraph "一维前缀和示意"
A["nums = [3, 1, 4, 1, 5, 9]"]
B["prefix = [0, 3, 4, 8, 9, 14, 23]"]
C["sum[l,r] = prefix[r+1] - prefix[l]"]
A --> B --> C
end代码实现：
#include <bits/stdc++.h>
using namespace std;
class PrefixSum {
private:
vector<int> prefix; // prefix[i] = sum(nums[0..i-1])
public:
// 构建前缀和数组，时间 O(n)
PrefixSum(vector<int>& nums) {
int n = nums.size();
prefix.resize(n + 1, 0);
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
}
// 查询区间 [l, r] 的和，时间 O(1)
// 注意：这里 l, r 是 0-indexed
int query(int l, int r) {
return prefix[r + 1] - prefix[l];
}
};
int main() {
vector<int> nums = {3, 1, 4, 1, 5, 9};
PrefixSum ps(nums);
cout << ps.query(1, 3) << endl; // 1+4+1 = 6
cout << ps.query(0, 5) << endl; // 3+1+4+1+5+9 = 23
cout << ps.query(2, 4) << endl; // 4+1+5 = 10
return 0;
}
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 构建前缀和 | \(O(n)\) | 遍历一遍数组 |
| 单次区间查询 | \(O(1)\) | 一次减法 |
前缀和的妙用
前缀和不仅用于求区间和，还可以：
- 求子数组和等于 k 的个数：prefix[j] - prefix[i] == k 转化为哈希表查找
- 判断是否存在和为 k 的子数组：一边计算前缀和一边查哈希表
7.6.2 二维前缀和¶
问题描述：给定一个二维矩阵，多次查询某个子矩阵的元素之和。
定义：prefix[i][j] 表示矩阵左上角 (0,0) 到右下角 (i-1,j-1) 这个矩形区域内所有元素的和。
graph TD
subgraph "二维前缀和公式"
A["prefix[i][j] = prefix[i-1][j] + prefix[i][j-1]<br/>- prefix[i-1][j-1] + matrix[i-1][j-1]"]
end
subgraph "区间查询公式"
B["sum(r1,c1,r2,c2) = prefix[r2+1][c2+1]<br/>- prefix[r1][c2+1] - prefix[r2+1][c1]<br/>+ prefix[r1][c1]"]
end代码实现：
#include <bits/stdc++.h>
using namespace std;
class MatrixPrefixSum {
private:
vector<vector<int>> prefix;
public:
// 构建二维前缀和
MatrixPrefixSum(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
prefix.assign(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1]
- prefix[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
// 查询以 (r1,c1) 为左上角，(r2,c2) 为右下角的子矩阵的和
int query(int r1, int c1, int r2, int c2) {
return prefix[r2 + 1][c2 + 1]
- prefix[r1][c2 + 1]
- prefix[r2 + 1][c1]
+ prefix[r1][c1];
}
};
int main() {
vector<vector<int>> matrix = {
{3, 0, 1, 4, 2},
{5, 6, 3, 2, 1},
{1, 2, 0, 1, 5},
{4, 1, 0, 1, 7},
{1, 0, 3, 0, 5}
};
MatrixPrefixSum mps(matrix);
cout << mps.query(1, 1, 3, 3) << endl; // 子矩阵 [6,3,2;2,0,1;1,0,1] 的和 = 16
return 0;
}
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 构建 | \(O(m \times n)\) | 遍历整个矩阵 |
| 单次查询 | \(O(1)\) | 四次查找 |
二维前缀和的记忆口诀
"多退少补"：prefix[r2+1][c2+1] 多加了两块（左和上），减掉后又多减了左上角，所以最后要加回来。
7.7 差分数组¶
7.7.1 差分数组的概念¶
差分数组是前缀和的逆运算。如果 prefix 是 nums 的前缀和，那么 nums 就是 prefix 的差分数组。
定义：diff[i] = nums[i] - nums[i-1]（diff[0] = nums[0]）。
核心性质：对差分数组做前缀和运算，就能还原出原数组。
graph TD
subgraph "前缀和与差分"
A["原数组 nums: [3, 1, 4, 1, 5, 9]"]
B["前缀和 prefix: [0, 3, 4, 8, 9, 14, 23]"]
C["差分 diff: [3, -2, 3, -3, 4, 4]"]
A -->|"前缀和"| B
B -->|"差分"| A
A -->|"差分"| C
C -->|"前缀和"| A
end7.7.2 差分数组的应用¶
核心优势：对原数组的区间加操作，在差分数组上只需修改两个端点。
区间加操作：对 nums[l..r] 每个元素加上 val：
代码实现：
#include <bits/stdc++.h>
using namespace std;
class Difference {
private:
vector<int> diff; // 差分数组
public:
// 根据原数组构建差分数组
Difference(vector<int>& nums) {
int n = nums.size();
diff.resize(n);
diff[0] = nums[0];
for (int i = 1; i < n; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
// 区间 [l, r] 每个元素加 val，时间 O(1)
void increment(int l, int r, int val) {
diff[l] += val;
if (r + 1 < (int)diff.size()) {
diff[r + 1] -= val;
}
}
// 将差分数组还原为结果数组，时间 O(n)
vector<int> result() {
vector<int> res(diff.size());
res[0] = diff[0];
for (int i = 1; i < (int)diff.size(); i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
};
int main() {
vector<int> nums = {1, 2, 3, 4, 5};
Difference diff(nums);
// 对区间 [1, 3] 每个元素加 2
diff.increment(1, 3, 2);
// 原数组变为: [1, 4, 5, 6, 5]
vector<int> ans = diff.result();
for (int x : ans) cout << x << " "; // 输出: 1 4 5 6 5
cout << endl;
// 再对区间 [2, 4] 每个元素加 3
diff.increment(2, 4, 3);
ans = diff.result();
for (int x : ans) cout << x << " "; // 输出: 1 4 8 9 8
cout << endl;
return 0;
}
| 操作 | 暴力方法 | 差分数组 |
|---|---|---|
| 单次区间加 | \(O(n)\) | \(O(1)\) |
| k 次区间加 + 一次查询 | \(O(kn)\) | \(O(k + n)\) |
差分数组适用场景
差分数组特别适合"多次区间修改 + 最后一次查询"的场景。如果需要在修改过程中频繁查询单点值，可以用树状数组或线段树替代。
7.8 分治简介：归并排序与逆序对¶
7.8.1 归并排序回顾¶
归并排序是分治的经典应用。将数组一分为二，分别排序后合并。其关键操作是合并两个有序数组，这正是分离双指针的应用。
graph TD
A["[38, 27, 43, 3, 9, 82, 10]"] --> B["[38, 27, 43, 3]"]
A --> C["[9, 82, 10]"]
B --> D["[38, 27]"]
B --> E["[43, 3]"]
C --> F["[9, 82]"]
C --> G["[10]"]
D --> H["[27, 38]"]
E --> I["[3, 43]"]
F --> J["[9, 82]"]
H --> K["合并: [3, 27, 38, 43]"]
I --> K
J --> L["合并: [9, 10, 82]"]
G --> L
K --> M["合并: [3, 9, 10, 27, 38, 43, 82]"]
L --> M7.8.2 归并排序代码¶
#include <bits/stdc++.h>
using namespace std;
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> temp;
int i = left, j = mid + 1;
// 分离双指针：合并两个有序子数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp.push_back(arr[i++]);
} else {
temp.push_back(arr[j++]);
}
}
while (i <= mid) temp.push_back(arr[i++]);
while (j <= right) temp.push_back(arr[j++]);
// 拷贝回原数组
for (int k = 0; k < (int)temp.size(); k++) {
arr[left + k] = temp[k];
}
}
void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); // 排序左半部分
mergeSort(arr, mid + 1, right); // 排序右半部分
merge(arr, left, mid, right); // 合并
}
| 复杂度 | 值 | 说明 |
|---|---|---|
| 时间 | \(O(n \log n)\) | 每层 \(O(n)\)，共 \(\log n\) 层 |
| 空间 | \(O(n)\) | 合并时需要临时数组 |
7.8.3 逆序对统计（剑指 Offer 51）¶
问题描述：在数组中，如果 i < j 且 nums[i] > nums[j]，则 (i, j) 是一个逆序对。求逆序对的总数。
思路分析：在归并排序的合并过程中统计逆序对。当右半部分的元素 arr[j] 先被选中时，说明它比左半部分中 [i, mid] 的所有元素都小，这些元素都与 arr[j] 构成逆序对。
graph LR
subgraph "合并时统计逆序对"
A["左半: [3, 5, 7] 右半: [1, 4, 6]"]
B["比较 3 和 1: 1 更小<br/>逆序对 += 3（1<3, 1<5, 1<7）"]
C["比较 3 和 4: 3 更小<br/>逆序对 += 0"]
A --> B --> C
end代码实现：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int mergeCount(vector<int>& nums, int left, int mid, int right) {
vector<int> temp;
int i = left, j = mid + 1;
int invCount = 0; // 逆序对计数
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp.push_back(nums[i++]);
} else {
// nums[i] > nums[j]，产生逆序对
// 左半部分 [i, mid] 的所有元素都 > nums[j]
invCount += (mid - i + 1);
temp.push_back(nums[j++]);
}
}
while (i <= mid) temp.push_back(nums[i++]);
while (j <= right) temp.push_back(nums[j++]);
for (int k = 0; k < (int)temp.size(); k++) {
nums[left + k] = temp[k];
}
return invCount;
}
int mergeSortCount(vector<int>& nums, int left, int right) {
if (left >= right) return 0;
int mid = left + (right - left) / 2;
int cnt = 0;
cnt += mergeSortCount(nums, left, mid);
cnt += mergeSortCount(nums, mid + 1, right);
cnt += mergeCount(nums, left, mid, right);
return cnt;
}
int reversePairs(vector<int>& nums) {
return mergeSortCount(nums, 0, nums.size() - 1);
}
};
int main() {
Solution sol;
vector<int> nums = {7, 5, 6, 4};
cout << sol.reversePairs(nums) << endl; // 输出 5
// 逆序对: (7,5), (7,6), (7,4), (5,4), (6,4)
return 0;
}
| 复杂度 | 值 | 说明 |
|---|---|---|
| 时间 | \(O(n \log n)\) | 归并排序的时间复杂度 |
| 空间 | \(O(n)\) | 合并时的临时空间 |
为什么在合并时统计？
归并排序保证了每次合并时左右两半各自有序。当 nums[i] > nums[j] 时，由于左半部分有序，nums[i..mid] 都大于 nums[j]，所以可以一次性统计多个逆序对，避免了暴力枚举的 \(O(n^2)\)。
练习题¶
扩展3 双指针（15题）¶
| 题号 | 题目 | 难度 | 链接 | 完成 |
|---|---|---|---|---|
| 88 | Merge Sorted Array | Easy | 链接 | - [ ] |
| 35 | Search Insert Position | Easy | 链接 | - [ ] |
| 350 | Intersection of Two Arrays II | Easy | 链接 | - [ ] |
| 326 | Power of Three | Easy | 链接 | - [ ] |
| 392 | Is Subsequence | Easy | 链接 | - [ ] |
| 16 | 3Sum Closest | Medium | 链接 | - [ ] |
| 18 | 4Sum | Medium | 链接 | - [ ] |
| 406 | Queue Reconstruction by Height | Medium | 链接 | - [ ] |
| 611 | Valid Triangle Number | Medium | 链接 | - [ ] |
| 491 | Non-decreasing Subsequences | Medium | 链接 | - [ ] |
| 42 | Trapping Rain Water | Hard | 链接 | - [ ] |
| 1147 | Longest Chunked Palindrome Decomposition | Hard | 链接 | - [ ] |
| 1793 | Maximum Score of a Good Subarray | Hard | 链接 | - [ ] |
| 2193 | Minimum Number of Moves to Make Palindrome | Hard | 链接 | - [ ] |
| 1755 | Closest Subsequence Sum | Hard | 链接 | - [ ] |
扩展4 滑窗&分治（12题）¶
| 题号 | 题目 | 难度 | 链接 | 完成 |
|---|---|---|---|---|
| 643 | Maximum Average Subarray I | Easy | 链接 | - [ ] |
| 219 | Contains Duplicate II | Easy | 链接 | - [ ] |
| 404 | Sum of Left Leaves | Easy | 链接 | - [ ] |
| 108 | Convert Sorted Array to Binary Search Tree | Easy | 链接 | - [ ] |
| 713 | Subarray Product Less Than K | Medium | 链接 | - [ ] |
| 109 | Convert Sorted List to Binary Search Tree | Medium | 链接 | - [ ] |
| 215 | Kth Largest Element in an Array | Medium | 链接 | - [ ] |
| 279 | Perfect Squares | Medium | 链接 | - [ ] |
| 220 | Contains Duplicate III | Hard | 链接 | - [ ] |
| 480 | Sliding Window Median | Hard | 链接 | - [ ] |
| 2106 | Maximum Fruits Harvested After at Most K Steps | Hard | 链接 | - [ ] |
| 493 | Reverse Pairs | Hard | 链接 | - [ ] |
寒假相关¶
| 题号 | 题目 | 难度 | 说明 | 链接 | 完成 |
|---|---|---|---|---|---|
| 11 | Container With Most Water | Medium | 对撞指针经典题，与盛水容器同类 | 链接 | - [ ] |
| 64 | Minimum Path Sum | Medium | 前缀和思想可用于部分优化 | 链接 | - [ ] |
| 300 | Longest Increasing Subsequence | Medium | 滑动窗口+二分优化的进阶题 | 链接 | - [ ] |
| 4 | Median of Two Sorted Arrays | Hard | 分离双指针 + 二分查找的经典难题 | 链接 | - [ ] |
寒假与暑假的衔接
寒假学习的数组遍历和基础搜索是双指针的基础。暑假的双指针与滑动窗口专题在此基础上引入了系统化的窗口维护和前缀和/差分等高级技巧，用以高效解决子串、子数组等区间类问题。
本章小结¶
| 小节 | 核心内容 | 关键技巧 |
|---|---|---|
| 7.1 双指针概述 | 对撞、快慢、分离三种模式 | 利用单调性将双重循环优化为线性 |
| 7.2 对撞指针 | 两数之和、三数之和、盛水容器 | 排序 + 左右逼近 + 去重 |
| 7.3 快慢指针 | 环检测、链表中点 | 慢 1 快 2 追及；入口推导 a=c |
| 7.4 滑动窗口模板 | 固定窗口、可变窗口 | right 扩 + left 缩 + 更新答案 |
| 7.5 滑动窗口经典 | 最长无重复子串、最小覆盖子串 | 哈希表维护窗口状态 + valid 计数 |
| 7.6 前缀和 | 一维、二维前缀和 | O(1) 区间查询；多退少补公式 |
| 7.7 差分数组 | 区间加操作 | O(1) 区间修改；最后还原 |
| 7.8 分治 | 归并排序 + 逆序对统计 | 合并时利用有序性统计逆序对 |