滑动窗口

问题描述

滑动窗口是一种在数组或字符串上使用双指针维护一个区间的技术。
通常，两个指针同向移动，通过动态更新区间内的信息来解决问题。

定长窗口

算法思想

维护固定大小的窗口
窗口右移时更新区间信息
适用于求解连续子数组的统计问题
时间复杂度 $\mathcal{O}(n)$

代码实现

c++
java
python

class Solution {
public:
    vector<double> movingAverage(vector<int>& nums, int k) {
        vector<double> result;
        int n = nums.size();
        if (n < k) return result;
        
        // 初始化第一个窗口
        double sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        result.push_back(sum / k);
        
        // 窗口滑动
        for (int i = k; i < n; i++) {
            sum = sum - nums[i-k] + nums[i];
            result.push_back(sum / k);
        }
        
        return result;
    }
};

class Solution {
    public double[] movingAverage(int[] nums, int k) {
        int n = nums.length;
        if (n < k) return new double[0];
        
        double[] result = new double[n - k + 1];
        
        // 初始化第一个窗口
        double sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        result[0] = sum / k;
        
        // 窗口滑动
        for (int i = k; i < n; i++) {
            sum = sum - nums[i-k] + nums[i];
            result[i-k+1] = sum / k;
        }
        
        return result;
    }
}

class Solution:
    def movingAverage(self, nums: List[int], k: int) -> List[float]:
        n = len(nums)
        if n < k:
            return []
        
        # 初始化第一个窗口
        window_sum = sum(nums[:k])
        result = [window_sum / k]
        
        # 窗口滑动
        for i in range(k, n):
            window_sum = window_sum - nums[i-k] + nums[i]
            result.append(window_sum / k)
        
        return result

不定长窗口

算法思想

使用双指针维护满足条件的窗口
右指针扩展窗口，左指针收缩窗口
动态维护窗口内的状态信息
更新最优解

代码实现

c++
java
python

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> count(128, 0);  // 字符计数
        int maxLen = 0;
        int left = 0, right = 0;
        
        while (right < s.length()) {
            count[s[right]]++;
            
            // 出现重复字符时收缩窗口
            while (count[s[right]] > 1) {
                count[s[left]]--;
                left++;
            }
            
            maxLen = max(maxLen, right - left + 1);
            right++;
        }
        
        return maxLen;
    }
};

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] count = new int[128];  // 字符计数
        int maxLen = 0;
        int left = 0, right = 0;
        
        while (right < s.length()) {
            count[s.charAt(right)]++;
            
            // 出现重复字符时收缩窗口
            while (count[s.charAt(right)] > 1) {
                count[s.charAt(left)]--;
                left++;
            }
            
            maxLen = Math.max(maxLen, right - left + 1);
            right++;
        }
        
        return maxLen;
    }
}

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_count = {}  # 字符计数
        max_len = left = 0
        
        for right, char in enumerate(s):
            char_count[char] = char_count.get(char, 0) + 1
            
            # 出现重复字符时收缩窗口
            while char_count[char] > 1:
                char_count[s[left]] -= 1
                left += 1
            
            max_len = max(max_len, right - left + 1)
        
        return max_len

时间复杂度分析

算法时间复杂度空间复杂度

定长窗口	$\mathcal{O}(n)$	$\mathcal{O}(1)$
不定长窗口	$\mathcal{O}(n)$	$\mathcal{O}(k)$
多指针窗口	$\mathcal{O}(n)$	$\mathcal{O}(k)$
计数窗口	$\mathcal{O}(n)$	$\mathcal{O}(\Sigma)$