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

这一课你将能做到

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
    }
}

O(n)，每个字符最多访问两次。

步骤 4：动态规划——爬楼梯

public class Main {
    public static int climbStairs(int n) {
        if (n <= 2) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
    
    // 空间优化 O(1)
    public static int climbStairsOpt(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
    
    public static void main(String[] args) {
        System.out.println(climbStairs(10));    // 89
        System.out.println(climbStairsOpt(10)); // 89
    }
}

步骤 5：动态规划——最长递增子序列

public class Main {
    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int maxLen = 1;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1; // 每个元素自己就是长度为1的递增子序列
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
    
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lengthOfLIS(nums)); // 4 (2,3,7,101)
    }
}

O(n²)，可用二分优化到 O(n log n)。

讲清楚要点

1. 双指针分类：对撞指针（两端向中间）、快慢指针（一快一慢，如检测环）、同向指针（滑动窗口）。
2. 滑动窗口核心：右指针扩张，左指针收缩，维护窗口内性质。关键是确定「何时收缩」。
3. DP 三要素：状态定义（dp[i] 表示什么）、状态转移方程（dp[i] 怎么从前面推出来）、初始条件（dp[0] 是多少）。
4. DP 优化方向：空间压缩（滚动数组）、状态精简、单调队列/二分加速。

你可能会懵的地方

• 双指针什么时候能用？ 数据有序（对撞），或需要满足某种单调性（同向）。无序时先排序，或考虑哈希表。

• 滑动窗口和双指针有什么区别？ 滑动窗口是双指针的特例：左右指针同向移动，维护窗口内性质。双指针范围更广。

• DP 和贪心怎么选？ 贪心每步选局部最优，不回溯；DP 考虑所有可能，记录子问题解。能用贪心解决的问题 DP 也能解，但反之不然。判断标准：是否具有「最优子结构」且「无后效性」。

• DP 数组开多大？ 通常开 n+1 或 n，看状态定义是否包含 0。多维 DP 注意内存，10^8 是上限。

• 怎么想到 DP 转移方程？ 从后往前想：「最后一步是什么？」比如爬楼梯，最后一步要么走 1 阶（从 n-1 来），要么走 2 阶（从 n-2 来）。

错法对照

错法	问题	正解
双指针忘记移动	死循环	每轮必须 left++ 或 right--
滑动窗口收缩条件错误	结果不对或死循环	明确「窗口内不满足什么条件就收缩」
DP 状态定义不清	转移方程写不出来	明确 dp[i] 的物理意义
DP 初始条件错误	边界结果错误	手动验证 dp[0]、dp[1]
空间优化维度弄反	覆盖未使用的状态	倒序遍历或明确新旧状态

卡点急救

1. 双指针结果不对：打印每轮 left、right、当前值，看是否符合预期。
2. 滑动窗口死循环：检查右指针是否每轮都移动。for (right++) 是标准写法。
3. DP 结果不对：打印 dp 数组，手动验证前几个值。或用暴力解法对拍。

面试常问

• 滑动窗口的模板是什么？

  int left = 0;
  for (int right = 0; right < n; right++) {
      // 扩张：加入 nums[right]
      while (窗口不满足条件) {
          // 收缩：移除 nums[left]
          left++;
      }
      // 更新答案
  }
  

• DP 和分治的区别？ 分治的子问题独立（如归并排序）；DP 的子问题重叠（如斐波那契）。DP 用记忆化或递推消除重复计算。

• 如何判断一个题能不能用 DP？ 三要素：最优子结构（最优解包含子问题最优解）、无后效性（未来不受过去影响）、重叠子问题（重复计算）。

自测三问

1. 双指针中「对撞指针」和「同向指针」分别适合什么场景？
2. 滑动窗口中，右指针和左指针的移动规则是什么？
3. 动态规划的三要素是什么？

小结一句话

双指针处理有序或单调问题，滑动窗口维护动态区间，动态规划拆解重叠子问题；掌握三大套路，中等题迎刃而解。

延伸

• Java 官方文档：数组与集合
• 下一课：刷题模式总结——常见题型与解题模板。