双指针、滑动窗口

一、双指针

双指针是指在算法中使用两个指针（通常是索引或迭代器）来解决问题，通过移动这两个指针来扫描数据结构（如数组或链表），从而达到高效的目的。双指针的核心思想是利用两个指针的相对位置或移动方式来减少时间复杂度，通常能将暴力解法的复杂度从 $O(n^2)$优化到 $O(n)$ 或 $O(n\log n)$。

1. 双指针的分类

双指针根据指针的移动方向和用途可以分为以下几种常见类型：

• 同向双指针（快慢指针）：两个指针同向移动，但速度不同，常用于链表或数组中寻找特定模式（如检测环、移除重复元素）。
• 相向双指针（左右指针）：两个指针从数组的两端向中间移动，常用于二分查找、两数之和等问题。
• 固定距离双指针：两个指针保持固定距离移动，常用于滑动窗口的简化场景。

2. 应用场景

• 数组/字符串的子序列、子数组问题
• 链表操作（找中点、检测环）
• 两数之和、三数之和等组合问题

3. 示例问题：两数之和 II（LeetCode 167）

问题描述：给定一个已按升序排列的数组 numbers 和一个目标值 target，找出两个数的下标（从1开始），使得它们的和等于 target。假设有且仅有一组解。

思路：

• 使用相向双指针，left 从数组开头，right 从数组末尾。
• 如果 numbers[left] + numbers[right] == target，返回结果。
• 如果和大于 target，右指针左移（减少和）；如果和小于 target，左指针右移（增加和）。

Python代码：

def twoSum(numbers: list[int], target: int) -> list[int]:
    left, right = 0, len(numbers) - 1
    while left < right:
        curr_sum = numbers[left] + numbers[right]
        if curr_sum == target:
            return [left + 1, right + 1]
        elif curr_sum < target:
            left += 1
        else:
            right -= 1
    return []

C++代码：

#include <vector>
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 curr_sum = numbers[left] + numbers[right];
            if (curr_sum == target) {
                return {left + 1, right + 1};
            } else if (curr_sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return {};
    }
};

时间复杂度：$O(n)$，因为每个指针最多移动 $n$ 次。
空间复杂度：$O(1)$，只用了常数额外空间。

4. 示例问题：快慢指针（移除数组中的重复元素，LeetCode 26）

问题描述：给定一个有序数组 nums，原地移除重复元素，返回新数组的长度。

思路：

• 使用快慢指针，slow 指向下一个不重复元素的位置，fast 遍历数组。
• 如果 nums[fast] != nums[slow-1]，将 fast 指向的元素复制到 slow 位置，slow 前进。

Python代码：

def removeDuplicates(nums: list[int]) -> int:
    if not nums:
        return 0
    slow = 1
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow - 1]:
            nums[slow] = nums[fast]
            slow += 1
    return slow

C++代码：

#include <vector>
using namespace std;

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int slow = 1;
        for (int fast = 1; fast < nums.size(); fast++) {
            if (nums[fast] != nums[slow - 1]) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
};

时间复杂度：$O(n)$，fast 遍历一次数组。
空间复杂度：$O(1)$，原地修改。

二、滑动窗口

滑动窗口是一种特殊的双指针技巧，适用于处理连续子数组或子字符串的问题。它通过维护一个动态调整大小的窗口（由两个指针定义），在遍历时不断扩展或收缩窗口来满足条件，从而高效解决问题。

1. 滑动窗口的核心思想

• 使用两个指针（left 和 right）表示窗口的边界。
• right 扩展窗口，直到窗口满足某种条件（或超出限制）。
• left 收缩窗口，直到窗口重新满足条件。
• 在窗口调整过程中记录答案（如最大长度、最小长度等）。

2. 应用场景

• 寻找最长/最短子数组或子字符串（如满足某种和、包含特定字符）
• 固定窗口大小的问题
• 动态窗口大小的问题

3. 示例问题：无重复字符的最长子串（LeetCode 3）

问题描述：给定一个字符串 s，找出其中不含重复字符的最长子串的长度。

思路：

• 使用滑动窗口，left 和 right 定义窗口。
• 用哈希表记录窗口内字符的最新位置。
• 当遇到重复字符时，left 跳到重复字符的下一个位置。
• 记录窗口的最大长度。

Python代码：

def lengthOfLongestSubstring(s: str) -> int:
    char_index = {}  # 记录字符最后出现的位置
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            left = char_index[s[right]] + 1  # 跳到重复字符的下一位
        char_index[s[right]] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

C++代码：

#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> char_index;
        int left = 0, max_length = 0;
        
        for (int right = 0; right < s.size(); right++) {
            if (char_index.find(s[right]) != char_index.end() && char_index[s[right]] >= left) {
                left = char_index[s[right]] + 1;
            }
            char_index[s[right]] = right;
            max_length = max(max_length, right - left + 1);
        }
        
        return max_length;
    }
};

时间复杂度：$O(n)$，每个字符最多被访问两次。
空间复杂度：$O(min(m,n))$，其中 $m$ 是字符集大小，$n$ 是字符串长度。

4. 示例问题：定长滑动窗口（LeetCode 643，最大平均值子数组）

问题描述：给定一个整数数组 `

nums和一个整数k，找出长度为k` 的连续子数组的最大平均值。

思路：

• 使用固定大小的滑动窗口，窗口大小为 k。
• 先计算前 k 个元素的和，然后滑动窗口，每次加一个新元素，减去窗口外的元素。
• 记录最大和，计算平均值。

Python代码：

def findMaxAverage(nums: list[int], k: int) -> float:
    curr_sum = sum(nums[:k])
    max_sum = curr_sum
    
    for i in range(k, len(nums)):
        curr_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, curr_sum)
    
    return max_sum / k

C++代码：

#include <vector>
using namespace std;

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        long curr_sum = 0;
        for (int i = 0; i < k; i++) {
            curr_sum += nums[i];
        }
        long max_sum = curr_sum;
        
        for (int i = k; i < nums.size(); i++) {
            curr_sum += nums[i] - nums[i - k];
            max_sum = max(max_sum, curr_sum);
        }
        
        return static_cast<double>(max_sum) / k;
    }
};

时间复杂度：$O(n)$，遍历数组一次。
空间复杂度：$O(1)$，只用了常数额外空间。

三、双指针与滑动窗口的区别与联系

• 双指针是更广义的概念，滑动窗口是双指针的一种特例。
• 滑动窗口通常用于处理连续子数组/子字符串问题，窗口大小可能是动态的（需满足条件）或固定的。
• 双指针可以有多种形式（如快慢指针、左右指针），不一定局限于窗口的概念。