滑动窗口与双指针技巧

算法滑动窗口双指针

算法

发布日期: 2024-09-21

作者: 小乐

文章字数: 816

阅读时长: 4 分

阅读次数:

一、双指针概述

1.1 核心思想

使用两个指针遍历数据结构，根据条件移动指针，将 ( O(n^2) ) 优化为 ( O(n) )。

1.2 常见类型

类型	特点	应用
对撞指针	从两端向中间移动	两数之和、回文判断
快慢指针	速度不同	环检测、找中点
滑动窗口	维护子数组/子串	子串问题、区间问题

二、对撞指针

2.1 两数之和（有序数组）

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};
        if (sum < target) left++;
        else right--;
    }
    return new int[]{-1, -1};
}

2.2 盛最多水的容器

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;
    
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);
        
        if (height[left] < height[right]) left++;
        else right--;
    }
    return maxArea;
}

2.3 三数之和

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = 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) {
                res.add(Arrays.asList(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 res;
}

三、快慢指针

3.1 检测链表环

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

3.2 找环入口

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    if (fast == null || fast.next == null) return null;
    
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

四、滑动窗口

4.1 固定窗口大小

public double[] findAverages(int[] nums, int k) {
    double[] res = new double[nums.length - k + 1];
    double sum = 0;
    
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (i >= k - 1) {
            res[i - k + 1] = sum / k;
            sum -= nums[i - k + 1];
        }
    }
    return res;
}

4.2 可变窗口 - 最小覆盖子串

public String minWindow(String s, String t) {
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    
    int left = 0, right = 0;
    int count = t.length();
    int minLen = Integer.MAX_VALUE;
    int start = 0;
    
    while (right < s.length()) {
        char c = s.charAt(right);
        if (need[c] > 0) count--;
        need[c]--;
        right++;
        
        while (count == 0) {
            if (right - left < minLen) {
                minLen = right - left;
                start = left;
            }
            char lc = s.charAt(left);
            need[lc]++;
            if (need[lc] > 0) count++;
            left++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

4.3 最长无重复子串

public int lengthOfLongestSubstring(String s) {
    int[] index = new int[128];
    int left = 0, maxLen = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        left = Math.max(left, index[c]);
        maxLen = Math.max(maxLen, right - left + 1);
        index[c] = right + 1;
    }
    return maxLen;
}