双指针 & 滑动窗口

概览

双指针的核心：用两个下标 left / right 代替两层嵌套循环。关键在于找到一个「单调性」：当一个指针移动时，另一个指针只需要往同一方向走，不会回头。这样两个指针各自最多走 n 步，总复杂度 O(n)。

四种常见模式

核心思维：维护窗口不变量

每步操作前后，窗口（或区间）必须满足某个条件。右指针扩展时可能破坏条件，此时收缩左指针直到条件恢复。这个「扩展-收缩」节奏是变长滑动窗口的本质。

复杂度

对向双指针

left 从左端出发，right 从右端出发，根据当前两元素的值决定移动哪个指针，直到相遇。前提：数组通常已排序（或可排序）。

核心思想

以 Two Sum（有序数组）为例：若 nums[left] + nums[right] == target，找到答案；若和偏小，left++ 使和增大；若和偏大，right-- 使和减小。每步都能排除一个元素，共 n 步。

步骤（Two Sum 有序版）

1. 初始化 left = 0，right = n - 1
2. 计算 sum = nums[left] + nums[right]
3. 若 sum == target，记录答案，退出
4. 若 sum < target，left++（增大左边元素使和变大）
5. 若 sum > target，right--（减小右边元素使和变小）
6. left >= right 时退出（无解）

C++ 实现

// Two Sum II — sorted array (1-indexed output)
pair<int,int> twoSum(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        if (sum == target) return {lo + 1, hi + 1};
        else if (sum < target) lo++;   // sum too small → move left up
        else                   hi--;   // sum too large → move right down
    }
    return {-1, -1};
}

适用场景

常见错误

同向双指针（快慢指针）

fast 和 slow 从同一侧出发，fast 负责探路，slow 负责标记「有效区域」的末尾。fast 每步必走，slow 只在满足条件时才前进。

核心思想

以原地删除重复元素为例：slow 指向当前去重后数组的末尾；fast 遍历每个元素，若与 slow 所指不同，则将其写入 ++slow 位置。最终 slow+1 即为新长度。

步骤（原地删除重复）

1. 初始化 slow = 0，fast 从 1 开始
2. fast 扫描每个元素
3. 若 nums[fast] != nums[slow]，令 nums[++slow] = nums[fast]
4. fast 到达末尾，返回 slow + 1

C++ 实现

// Remove Duplicates from Sorted Array (in-place)
int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int slow = 0;                        // tail of unique prefix
    for (int fast = 1; fast < (int)nums.size(); fast++) {
        if (nums[fast] != nums[slow])
            nums[++slow] = nums[fast];   // write new unique element
    }
    return slow + 1;                     // new length
}

适用场景

常见错误

定长滑动窗口

窗口大小固定为 k，整体向右滑动。每次移入一个新元素（右侧），同时移出最旧元素（左侧），维护窗口内的聚合值（sum、max、freq 等）。

核心思想

先计算第一个窗口 [0, k-1] 的结果，然后循环：windowSum += nums[i] - nums[i-k]。这样每次只做 O(1) 的增量更新，而非重新计算，从而把 O(nk) 降到 O(n)。

步骤（最大子数组和，窗口大小 k）

1. 计算初始窗口 [0, k-1] 的和，令 maxSum = windowSum
2. i 从 k 到 n-1 循环（i 是新进入窗口的元素）
3. windowSum += nums[i] - nums[i - k]（加新元素，减最旧元素）
4. maxSum = max(maxSum, windowSum)
5. 返回 maxSum

C++ 实现

// Maximum sum of any subarray of size k
int maxSumWindow(vector<int>& nums, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += nums[i]; // first window
    int maxSum = windowSum;
    for (int i = k; i < (int)nums.size(); i++) {
        windowSum += nums[i] - nums[i - k]; // slide: add right, drop left
        maxSum = max(maxSum, windowSum);
    }
    return maxSum;
}

适用场景

常见错误

变长滑动窗口

窗口大小不固定，右指针持续扩张，左指针按照「窗口是否违反约束」来收缩。两个指针合计移动 O(n) 次，整体 O(n)。

核心思想

right 每次向右扩一位，将 s[right] 加入窗口；若窗口违反约束（如出现重复字符），不断 left++ 直到窗口合法；此时 [left, right] 是以 right 结尾的最长合法窗口，更新答案。

步骤（最长无重复字符子串）

1. 初始化 left = 0，freq 计数器，ans = 0
2. right 从 0 到 n-1 循环，将 s[right] 加入 freq
3. 若 freq[s[right]] > 1（出现重复），收缩：freq[s[left]]--, left++
4. 更新 ans = max(ans, right - left + 1)
5. 返回 ans

C++ 实现

// Longest Substring Without Repeating Characters
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> freq;
    int ans = 0, left = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        freq[s[right]]++;
        while (freq[s[right]] > 1) {   // duplicate → shrink from left
            freq[s[left]]--;
            left++;
        }
        ans = max(ans, right - left + 1);
    }
    return ans;
}

常见约束类型

常见错误

LeetCode 题型

按模式分类的高频双指针题目。

对向双指针

同向双指针

定长滑动窗口

变长滑动窗口