跳到主要内容

双指针与滑动窗口

问题​

双指针和滑动窗口有哪些常见题型？

答案​

双指针分类​

类型说明典型题目
对撞指针左右向中间移动两数之和（有序）、接雨水
快慢指针不同速度移动链表有环、移除元素
滑动窗口维护一段区间最长无重复子串、最小覆盖子串

两数之和（有序数组）​

对撞指针
public int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;
        else right--;
    }
    return new int[]{};
}

三数之和​

排序 + 双指针
public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;  // 去重
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.add(List.of(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--;
            } else if (sum < 0) left++;
            else right--;
        }
    }
    return result;
}

最长无重复字符子串（滑动窗口）​

滑动窗口
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, maxLen = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        window.merge(c, 1, Integer::sum);
        
        // 窗口内有重复字符，收缩左边界
        while (window.get(c) > 1) {
            char d = s.charAt(left);
            window.merge(d, -1, Integer::sum);
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

滑动窗口模板​

通用模板
int left = 0;
for (int right = 0; right < n; right++) {
    // 1. 扩大窗口：加入 right 元素
    window.add(arr[right]);
    
    // 2. 判断是否需要收缩
    while (needShrink()) {
        // 3. 收缩窗口：移出 left 元素
        window.remove(arr[left]);
        left++;
    }
    
    // 4. 更新结果
    result = Math.max(result, right - left + 1);
}

常见面试问题​

Q1: 接雨水怎么做？​

答案：

双指针法：分别从左右向中间移动，维护左右的最大高度。

public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            leftMax = Math.max(leftMax, height[left]);
            water += leftMax - height[left];
            left++;
        } else {
            rightMax = Math.max(rightMax, height[right]);
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

Q2: 移动零（原地操作）​

答案：

快慢指针：slow 指向下一个非零元素应该放的位置。

public void moveZeroes(int[] nums) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            int temp = nums[slow];
            nums[slow] = nums[fast];
            nums[fast] = temp;
            slow++;
        }
    }
}

相关链接​