面试重要程度：⭐⭐⭐⭐⭐

常见提问方式： "手写双指针算法" "实现滑动窗口" "KMP字符串匹配原理"

预计阅读时间：40分钟

🎯 双指针技巧

对撞指针

/**
 * 双指针经典问题解决方案
 */
public class TwoPointerSolutions {
    
    /**
     * 两数之和 - 有序数组版本
     * LeetCode 167: Two Sum II - Input array is sorted
     */
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1}; // 题目要求1-indexed
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        
        return new int[]{-1, -1}; // 未找到
    }
    
    /**
     * 三数之和
     * LeetCode 15: 3Sum
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // 先排序
        
        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;
            int target = -nums[i];
            
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    result.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 < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return result;
    }
    
    /**
     * 盛最多水的容器
     * LeetCode 11: Container With Most Water
     */
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxWater = 0;
        
        while (left < right) {
            int width = right - left;
            int currentWater = Math.min(height[left], height[right]) * width;
            maxWater = Math.max(maxWater, currentWater);
            
            // 移动较短的指针
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxWater;
    }
    
    /**
     * 回文字符串验证
     * LeetCode 125: Valid Palindrome
     */
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        
        while (left < right) {
            // 跳过非字母数字字符
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            
            if (Character.toLowerCase(s.charAt(left)) != 
                Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            
            left++;
            right--;
        }
        
        return true;
    }
}

快慢指针

/**
 * 快慢指针应用
 */
public class FastSlowPointer {
    
    /**
     * 移除重复元素
     * LeetCode 26: Remove Duplicates from Sorted Array
     */
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        
        int slow = 0; // 慢指针指向不重复元素的末尾
        
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }
        
        return slow + 1;
    }
    
    /**
     * 移动零
     * LeetCode 283: Move Zeroes
     */
    public void moveZeroes(int[] nums) {
        int slow = 0; // 慢指针指向非零元素的末尾
        
        // 第一遍：将非零元素移到前面
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        
        // 第二遍：将剩余位置填充为0
        while (slow < nums.length) {
            nums[slow] = 0;
            slow++;
        }
    }
    
    /**
     * 颜色分类（荷兰国旗问题）
     * LeetCode 75: Sort Colors
     */
    public void sortColors(int[] nums) {
        int left = 0, right = nums.length - 1;
        int current = 0;
        
        while (current <= right) {
            if (nums[current] == 0) {
                swap(nums, left, current);
                left++;
                current++;
            } else if (nums[current] == 2) {
                swap(nums, current, right);
                right--;
                // 注意：这里current不自增，因为交换过来的元素还需要检查
            } else {
                current++;
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

🪟 滑动窗口算法

固定窗口大小

/**
 * 滑动窗口算法实现
 */
public class SlidingWindowSolutions {
    
    /**
     * 长度为K的子数组的最大值
     * LeetCode 239: Sliding Window Maximum
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 0) return new int[0];
        
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>(); // 存储索引
        
        for (int i = 0; i < nums.length; i++) {
            // 移除窗口外的元素
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            
            // 移除比当前元素小的元素（保持单调递减）
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            
            deque.offerLast(i);
            
            // 当窗口大小达到k时，记录最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
    
    /**
     * 字符串中所有字母异位词
     * LeetCode 438: Find All Anagrams in a String
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) return result;
        
        int[] pCount = new int[26];
        int[] windowCount = new int[26];
        
        // 统计p中字符频率
        for (char c : p.toCharArray()) {
            pCount[c - 'a']++;
        }
        
        int windowSize = p.length(