🧰 解题技巧
双指针 · 滑动窗口 · 前缀和 · 差分 · 位运算 · 单调栈
1. 双指针的三种形态？
- 对撞指针：左右向中间靠。适合有序数组：两数之和、三数之和、盛水容器、回文判断、反转字符串
- 快慢指针：一个快一个慢。适合链表/数组：环检测、找中点、删除倒数第 N、去重（原地）、移动零
- 同向双指针：两个指针同向移动（即滑动窗口，见下）
原地去重（快慢指针，经典）
// 有序数组原地去重，返回新长度
public int removeDuplicates(int[] a) {
int slow = 0;
for (int fast = 1; fast < a.length; fast++)
if (a[fast] != a[slow]) a[++slow] = a[fast]; // slow 指向已去重末尾
return slow + 1;
}🎯 面试要点
- 双指针的核心收益：把 O(n²) 暴力降为 O(n)——"排序 + 双指针"是数组题万能起点
- 对撞指针要求有序性（自己排序或题目有序）；快慢指针注意 null/边界
2. 滑动窗口模板？（子串/子数组题万能）
适用：连续子串/子数组问题——最长/最短满足条件的窗口。核心：右指针扩展，窗口不满足条件时收缩左指针。
滑动窗口通用框架
int left = 0, len = 0;
Map<Character, Integer> window = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
window.merge(c, 1, Integer::sum); // ① 右扩：进窗口
while (需要收缩(窗口)) { // ② 不满足条件：收缩
char d = s.charAt(left++);
window.merge(d, -1, Integer::sum); // 出窗口
if (window.get(d) == 0) window.remove(d);
}
len = Math.max(len, right - left + 1); // ③ 更新答案（最长/最短不同写法）
}
return len;🎯 面试要点
- "最长无重复子串"、"最小覆盖子串"、"字符串排列"都是这模板；收缩条件是每题的差异点
- 窗口计数用数组（int[26] 或 int[128]）比 HashMap 更快
3. 前缀和与差分？
- 前缀和：
pre[i] = sum(a[0..i-1])，则子数组 [l, r) 的和 = pre[r] - pre[l]，O(1) 查区间和。适用：子数组和为 k、二维矩阵区域和、差分统计 - 前缀和 + 哈希：找"和为 k 的子数组个数"——遍历时存 pre 值出现次数，O(n)
- 差分：区间统一加值用差分数组（diff[l]+=v, diff[r+1]-=v），最后前缀和还原
和为 k 的子数组个数（前缀和 + Map）
public int subarraySum(int[] a, int k) {
Map<Integer, Integer> count = new HashMap<>();
count.put(0, 1); // pre=0 出现 1 次（空前缀）
int pre = 0, ans = 0;
for (int x : a) {
pre += x;
ans += count.getOrDefault(pre - k, 0); // 之前出现过 pre-k 的次数
count.merge(pre, 1, Integer::sum);
}
return ans;
}🎯 面试要点
- 区间和/计数问题先想前缀和；二维版：prefix[i][j] = 区域和，容斥公式
- "pre - k 出现过多少次"是计数型题目的核心转化
4. 位运算技巧 & 单调栈？
位运算：
- x & (x-1)：消去最低位的 1 → 数二进制 1 的个数
- x ^ x = 0，x ^ 0 = x → 找只出现一次的数（其他成对）
- n & 1 判奇偶；左移 ×2 右移 ÷2（注意负数符号位）
- x & (-x)：取最低位的 1
单调栈：栈内元素保持单调（递增/递减）。典型应用：下一个更大元素、每日温度、柱状图最大矩形。模板：遍历时维护单调栈，出栈时结算答案。
下一个更大元素（单调递减栈）
public int[] nextGreater(int[] a) {
int[] res = new int[a.length];
Deque<Integer> stack = new ArrayDeque<>(); // 存下标
for (int i = a.length - 1; i >= 0; i--) { // 从右往左
while (!stack.isEmpty() && a[stack.peek()] <= a[i]) stack.pop();
res[i] = stack.isEmpty() ? -1 : a[stack.peek()];
stack.push(i);
}
return res;
}🎯 面试要点
- 单调栈的直觉：栈里存"还没找到答案的候选"，弹出即结算
- 循环数组版（下一个更大元素 II）：数组拉长两倍取模即可
- 位运算面试量少但考到要秒答：异或去重、与消位是最常考两个