二分法补充——力扣209. 长度最小的数组

原题链接

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

思路

​ 题目显然使用暴力的方法会超时，比较容易联想到使用前缀合+二分查找答案，即通过前缀合预先处理数组来降低后续查找答案的时间复杂度，然后通过二分查找逼近最小的满足题目要求的答案，复杂度为nlognnlogn，二分查找的初始化上限为nn，下限为11，代码如下：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        vector<int> sums(n + 1);
        for(int i = 1; i <= n; i ++){
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        int l = 1, r = n;
        while(l < r){
            int mid = (l + r + 1) >> 1;
            bool flag = false;
            for(int i = 1; i <= n - mid + 1; i ++){
                int tmp = sums[i + mid - 1] - sums[i - 1];
                if(tmp >= target){
                    flag = true;
                    break;
                } 
            }
            if(flag){
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        if(l == n && sums[n] < target){
            return 0;
        }
        return l;
    }
};

补充

二分查找有两种最核心的变体：寻找左边界（最小值） 和 寻找右边界（最大值）

写法一：寻找“满足条件的最小值” (左边界)

while(l < r){
    int mid = (l + r) >> 1; // 向下取整
    if(check(mid)){   // check() 函数判断 mid 是否满足条件
        r = mid;      // 满足条件：mid 可能是答案，保留它，尝试更小的
    }else{
        l = mid + 1;  // 不满足：mid 肯定不是答案，丢弃它，往右找
    }
}

核心特征与场景

  • 目标：寻找满足 check(mid) 为 true 的 最小值。
  • 策略：
    • 如果 mid 满足条件，它是潜在的“最小值”，所以不能丢弃，必须 r = mid。
    • 如果 mid 不满足，说明太小了，必须 l = mid + 1。
  • mid 取法：因为出现了 r = mid，必须配合 向下取整 (l + r) >> 1。

写法二：寻找“满足条件的最大值” (右边界)

while(l < r){
    int mid = (l + r + 1) >> 1; // 向上取整！
    if(check(mid)){   // check() 函数判断 mid 是否满足条件
        l = mid;      // 满足条件：mid 可能是答案，保留它，尝试更大的
    }else{
        r = mid - 1;  // 不满足：mid 肯定不是答案，丢弃它，往左找
    }
}

核心特征与场景

  • 目标：寻找满足 check(mid) 为 true 的 最大值。
  • 策略：
    • 如果 mid 满足条件，它是潜在的“最大值”，所以不能丢弃，必须 l = mid。
    • 如果 mid 不满足，说明太大了（或者不符合要求），必须 r = mid - 1。
  • mid 取法：因为出现了 l = mid，必须配合 向上取整 (l + r + 1) >> 1。

因果关系与 mid 取整

为什么 mid 的写法会不同？这是由 死循环的边界条件 倒逼出来的：

二分查找的死循环总是发生在区间只剩 2 个数时（例如 l = 2, r = 3）。

  • 针对写法一 (r = mid)：
    • 如果我们用向上取整 (2+3+1)/2 = 3，此时 mid = r。
    • 如果走进 r = mid 分支，r 还是 3，l 还是 2。死循环！
    • 结论：只要你有 r = mid，mid 必须向下取整 (l + r) >> 1，保证 mid 偏向 l，这样 r 才会变小。
  • 针对写法二 (l = mid)：
    • 如果我们用向下取整 (2+3)/2 = 2，此时 mid = l。
    • 如果走进 l = mid 分支，l 还是 2，r 还是 3。死循环！
    • 结论：只要你有 l = mid，mid 必须向上取整 (l + r + 1) >> 1，保证 mid 偏向 r，这样 l 才会变大。