引言：算法选择的十字路口

在算法面试中，双指针和滑动窗口如同两把瑞士军刀，能高效解决80%以上的数组和字符串问题。本文将深入解析这两种技术的核心差异，结合力扣高频题目，提供可直接复用的代码。

一、算法核心思想解析

1. 双指针技术

双指针算法是通过维护‌两个指针变量‌（通常为数组/链表索引）协同遍历数据结构的高效策略，主要用于优化暴力解法的时空复杂度。

‌三种经典模式‌：

‌对撞指针‌：首尾指针向中间收敛（如三数之和）
‌快慢指针‌：同向移动但速度不同（如环形链表检测）
‌滑动窗口‌：动态维护子区间（特殊双指针实现）

2. 滑动窗口技术

作为双指针的特殊形式，滑动窗口具有以下特点：

两个指针‌同向移动‌且‌维护一个连续区间
通过窗口扩张/收缩动态调整解空间

3. 算法特性对比

特性	双指针算法	滑动窗口算法
‌指针移动方向‌	可对撞/同向	严格同向移动
‌数据要求‌	常需排序	原始数据即可
‌时间复杂度‌	O(n)~O(n²)	O(n)
‌典型问题‌	有序数组组合问题	子串/子数组最优解
‌状态维护‌	通常不需要	需要哈希表记录状态

二、高频面试题分类精讲

1. 双指针经典题型：三数之和（LeetCode 15）

解题思路：

1. 暴力解法（不推荐）

最直观的方法是三重循环遍历所有可能的三元组，时间复杂度为O(n³)，效率太低。

2. 排序 + 双指针法（推荐）

‌步骤如下：‌

‌排序数组‌：首先将数组排序，这样可以利用有序性来优化搜索
‌固定一个数‌：遍历数组，将当前元素作为第一个数
‌双指针搜索‌：在当前元素后面的部分使用双指针（左指针从当前元素后一位开始，右指针从数组末尾开始）寻找另外两个数
‌去重处理‌：跳过重复的元素以避免重复解

‌时间复杂度‌：O(n²)（排序O(nlogn) + 双指针遍历O(n²)）

public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();int length = nums.length;if (nums == null || length < 3) {return result;}Arrays.sort(nums);  // 关键步骤：排序for (int i =0; i < length; i++) {// 需要和上一次枚举的数不相同if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i+1;int right = length - 1;int target = -nums[i]; // nums[left] + nums[right] = targetwhile(left < right) {int sum = nums[left] + nums[right];if (sum == target) {result.add(Arrays.asList(nums[i], nums[left], nums[right]));// 跳过重复的left和rightwhile (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;}

2. 滑动窗口经典题型：最小覆盖子串（LeetCode 76）

算法核心思想

‌ 滑动窗口（Sliding Window）算法‌是解决最小覆盖子串问题的最优方法：

‌双指针定义窗口‌：使用left和right两个指针表示当前考察的子串窗口
‌哈希表记录需求‌：使用两个哈希表分别存储：

need：目标字符串T中各字符的需求量
window：当前窗口中满足需求的字符数量

3. 动态扩展收缩窗口‌：

先扩展right指针寻找可行解
再收缩left指针优化解

4. 有效字符计数‌：通过valid变量统计窗口中已满足需求的字符种类数

5. 实时更新结果‌：每当找到更小的满足条件的子串时更新结果

复杂度分析

‌时间复杂度‌：O(n)，其中n是字符串S的长度
‌空间复杂度‌：O(m)，其中m是字符集大小（通常为常数级）

Java实现代码

public String minWindow(String s, String t) {// 边界条件检查if (s == null || t == null || s.length() < t.length()) {return "";}// 初始化需求哈希表，记录t中每个字符出现的次数Map<Character, Integer> need = new HashMap<>();for (char c : t.toCharArray()) {need.put(c, need.getOrDefault(c, 0) + 1);}// 初始化窗口哈希表，记录当前窗口中满足需求的字符数量Map<Character, Integer> window = new HashMap<>();// 记录窗口中满足need条件的字符个数int valid = 0;// 记录最小覆盖子串的起始位置和长度int start = 0, minLen = Integer.MAX_VALUE;// 滑动窗口左右指针int left = 0, right = 0;while (right < s.length()) {// 获取右指针当前字符char c = s.charAt(right);// 右指针向右移动right++;// 如果当前字符在需求表中，则更新窗口计数if (need.containsKey(c)) {window.put(c, window.getOrDefault(c, 0) + 1);// 如果窗口中该字符数量等于需求数量，则valid加1if (window.get(c).equals(need.get(c))) {valid++;}}// 当窗口满足所有字符需求时，尝试收缩左边界while (valid == need.size()) {// 更新最小覆盖子串信息if (right - left < minLen) {start = left;minLen = right - left;}// 获取左指针当前字符char d = s.charAt(left);// 左指针向右移动left++;// 如果移出的字符在需求表中，则更新窗口计数if (need.containsKey(d)) {// 如果窗口中该字符数量刚好等于需求数量，则valid减1if (window.get(d).equals(need.get(d))) {valid--;}window.put(d, window.get(d) - 1);}}}// 返回最小覆盖子串，如果没有找到则返回空字符串return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);}

三、算法选择的核心判别特征

1. 双指针算法的识别特征

当问题呈现以下‌至少两个‌特征时，优先考虑双指针算法：

‌线性序列结构‌（数组/链表）
- 典型表现：输入数据为数组或链表等线性结构
- 反例：树形结构或图结构通常不适用
‌有序性或可排序性‌
- 典型表现：题目明确说明"已排序"或允许预处理排序
- 示例特征："非递减顺序排列"、"你可以假设数组已经按升序排列"
‌对称性/双向操作需求‌
- 典型表现：需要从两端向中间或特定方向协同操作
- 示例场景：回文判断、盛水容器问题
‌组合优化问题‌
- 典型表现：需要寻找两个或多个元素的特定组合
- 示例模式："找出满足条件的两个元素"、"确定三个数的组合"

2. 滑动窗口算法的识别特征

当问题呈现以下‌至少两个‌特征时，优先考虑滑动窗口算法：

‌连续子区间要求‌
- 典型表现：需要处理数组中连续的序列或子串
- 关键词："连续子数组"、"子串"、"连续的...满足条件"
‌窗口可变或固定大小‌
- 典型表现：需要动态调整或保持固定大小的区间
- 可变窗口特征："最短/最长满足条件的..."
- 固定窗口特征："大小为k的..."
‌统计类约束条件‌
- 典型表现：基于频率、和、平均值等统计量的条件判断
- 示例条件："包含所有字符"、"和≥target"、"无重复字符"
‌最优解搜索‌
- 典型表现：需要寻找满足特定条件的最优区间
- 典型目标："最小的...满足..."、"最大的...满足..."