第四章 算法优化实战：双指针、滑动窗口与二分变种

算法优化，说白了就是让代码跑得更快、用得更少。很多同学一上来就撸暴力解法，跑通了就完事。但真实项目里，数据量一上来，暴力解法直接崩给你看。我这些年踩过的坑，十有八九都是算法选型不当造成的。

这一章，我们聚焦四个高频优化技巧：双指针、滑动窗口、前缀和与差分、二分查找变种。它们不是花架子，是实打实能帮你把 O(n²) 降到 O(n) 甚至 O(log n) 的利器。

4.1 双指针：两个指针走天下

双指针，就是用一个循环、两个下标来遍历。一个从头，一个从尾；或者一个快，一个慢。它能把两层循环压成一层。

典型场景：

• 对撞指针：有序数组两数之和、回文判断、反转数组
• 快慢指针：链表环检测、删除倒数第 N 个节点
• 分离指针：数组奇偶分离、颜色分类

举个例子，两数之和 II - 输入有序数组：

// 暴力解法 O(n²)
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (nums[i] + nums[j] == target) return {i, j};
    }
}

// 双指针 O(n)
int left = 0, right = n - 1;
while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) return {left, right};
    else if (sum < target) left++;
    else right--;
}

我在项目中遇到过类似场景：一个日志分析系统需要找出时间戳之和等于目标值的两条记录。数据量百万级，暴力解法跑了 3 秒多，换成双指针后降到 20 毫秒。嗯，差距就是这么大。

4.2 滑动窗口：子数组问题的标准答案

滑动窗口，说白了就是维护一个区间，让这个区间在数组上滑来滑去。它专门解决「连续子数组」类问题。

两种窗口：

可变窗口的通用模板：

int left = 0;
for (int right = 0; right < n; right++) {
    // 1. 扩展窗口：加入 nums[right]
    // 2. 收缩窗口：当窗口不满足条件时，移动 left
    while (窗口不满足条件) {
        // 移除 nums[left]
        left++;
    }
    // 3. 更新答案
}

我记得有一次做用户行为分析，要找出「连续点击次数超过 100 次的最长时段」。暴力解法 O(n²) 跑了 5 分钟没出结果。换成滑动窗口后，O(n) 秒出。你想想看，这就是优化的魅力。

4.3 前缀和与差分：区间查询的加速器

前缀和，就是提前算好「从开头到每个位置的和」。这样查询任意区间 [l, r] 的和，只需要 O(1) 时间。

一维前缀和：

// 预处理
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}

// 查询区间 [l, r] 的和
int sum = prefix[r + 1] - prefix[l];  // O(1)

差分数组是前缀和的逆运算。它专门处理「区间批量加减」操作。

我曾经接手过一个排班系统，每天要处理上千次「某段时间内增加 N 个人手」的请求。一开始用暴力循环，每次 O(n)，系统响应越来越慢。改成差分数组后，每次操作 O(1)，最后统一还原，性能提升了 100 倍。

4.4 二分查找的变种：不只是找中间值

标准的二分查找大家都会。但真实场景里，我们经常需要找「第一个大于等于 target 的位置」或者「最后一个小于等于 target 的位置」。这就是二分查找的变种。

四种常见变种：

• 左边界：第一个 >= target 的位置（lower_bound）
• 右边界：最后一个 <= target 的位置（upper_bound - 1）
• 第一个 > target：upper_bound
• 最后一个 < target：lower_bound - 1

左边界二分模板：

int left = 0, right = n;  // 注意 right 开区间
while (left < right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] >= target) {
        right = mid;  // 收缩右边界
    } else {
        left = mid + 1;
    }
}
return left;  // 第一个 >= target 的位置

为什么用 left + (right - left) / 2？防止 left + right 溢出。嗯，这个细节面试经常考。

4.5 综合实战：一道题串起四个技巧

来看一道综合题：给定一个数组，求所有和为 target 的子数组个数。

这道题可以用多种方法解，正好串起本章四个技巧：

前缀和 + 哈希表解法：

int subarraySum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);  // 前缀和为 0 出现 1 次
    int prefix = 0, count = 0;
    for (int num : nums) {
        prefix += num;
        // 如果存在 prefix - target，说明有子数组和为 target
        count += map.getOrDefault(prefix - target, 0);
        map.put(prefix, map.getOrDefault(prefix, 0) + 1);
    }
    return count;
}

这个解法我用了很多年。它把 O(n²) 的问题降到了 O(n)，而且代码很简洁。你想想看，如果面试官问你「还有没有更好的方法」，你能从暴力 -> 前缀和 -> 前缀和+哈希表，一路优化上去，这就是跃迁。