算法技巧：双指针、滑动窗口与动态规划入门

这一课你将能做到

1. 用双指针解决「两数之和」「回文判断」等问题
2. 用滑动窗口解决「最长无重复子串」「最小覆盖子串」等问题
3. 用动态规划解决「爬楼梯」「最长递增子序列」等入门问题

为什么要学

技巧是算法的「套路」。掌握双指针、滑动窗口、DP 三大套路，80% 的中等题都有思路。不会技巧，遇到新题就只能干瞪眼。

人话：双指针是「两个人从两端往中间走」；滑动窗口是「可伸缩的放大镜」；动态规划是「把大问题拆成小问题，记下来不重复算」。

先建立图像

双指针（对撞）:
[1, 2, 3, 4, 5, 6]  target=7
 ↑                 ↑
 left             right
 1+6=7 ✓

滑动窗口:
[a, b, c, a, b, c, b, b]
    [窗口]
       [窗口]
         [窗口]     ← 维持无重复

动态规划:
爬楼梯: f(n) = f(n-1) + f(n-2)
        1, 2, 3, 5, 8, 13...

跟着做

步骤 1：双指针——两数之和（有序数组）

public class Main {
    public static 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};
    }
    
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int[] res = twoSum(nums, 9);
        System.out.println(res[0] + ", " + res[1]); // 0, 1
    }
}

O(n)，前提是数组已排序。未排序用哈希表。

步骤 2：双指针——判断回文

public class Main {
    public static 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 static void main(String[] args) {
        System.out.println(isPalindrome("A man, a plan, a canal: Panama")); // true
    }
}

步骤 3：滑动窗口——最长无重复子串

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> lastIndex = new HashMap<>();
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (lastIndex.containsKey(c) && lastIndex.get(c) >= left) {
                left = lastIndex.get(c) + 1; // 窗口左边界右移
            }
            lastIndex.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
    
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
        System.out.println(lengthOfLongestSubstring("bbbbb"));    // 1
        System.out.println(lengthOfLongestSubstring("pwwkew"));   // 3
    }
}