🌕 209. 长度最小的子数组

难度: 🌕

• 问题描述
• 解法 1 - 双指针
• 输出 1
• 解法 2 - 前缀和 + 二分
• 输出 2

问题描述

---

解法 1 - 双指针

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 思路:
        // 滑动窗口
        int len = nums.length;
        int left = 0;
        int right = 0;
        int res = len + 1;
        int sum = nums[0];
        while(left < len) {
            // 找满足条件的最小右边界
            while(right < len - 1 && sum < target) {
                right ++;
                sum += nums[right];
            }
            // System.out.println("right: " + right + " sum : " + sum);
            // right == len || sum >= target
            // 缩小左边界
            while(left <= right && sum - nums[left] >= target) {
                sum -= nums[left];
                left ++;
            }
            // System.out.println("left: " + left + " sum : " + sum);
            if(sum >= target) {
                res = Math.min(res, right - left + 1);
            } else {
                break;
            }
            sum -= nums[left];
            left ++;
        }
        if(res == len + 1) {
            return 0;
        }
        return res;
    }
}

---

输出 1

---

解法 2 - 前缀和 + 二分

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 思路:
        // 求每个下标处的前缀和 sum[i] = [0, i] 的和
        // 目标： sum[i] - sum[?] >= target
        // sum[?] <= sum[i] - target
        // 二分查找加快速度
        int len = nums.length;
        int[] sum = new int[len];
        sum[0] = nums[0];
        for(int i = 1; i < len; i ++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        // 遍历每个节点，找到达到目标所需最小长度
        int res = len + 1;
        for(int i = 0; i < len; i ++) {
            if(sum[i] < target) {
                continue;
            } else if(sum[i] == target) {
                res = Math.min(res, i + 1);
            } else {
                res = Math.min(res, i + 1);
                // sum[i] > target
                // 可以缩进左边界
                int aim = sum[i] - target;
                // 找到某个 下标 处 sum[?] <= aim
                if(sum[0] > aim) {
                    continue; // 说明首节点一定不能缩进，更别提再往前缩进了
                }
                int left = mySol(sum, aim, 0, i);
                res = Math.min(res, i - left); // 画图理解
            }
        }
        if(res == len + 1) {
            return 0;
        }
        return res;
    }

    private int mySol(int[] array, int target, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            return left;
        }
        // left < right
        int mid = left + ((right - left) >> 1) + 1;
        if(array[mid] == target) {
            // 无重复数组
            return mid;
        } else if(array[mid] > target) {
            right = mid - 1;
            return mySol(array, target, left, right);
        } else {
            // [mid] < target
            left = mid;
            return mySol(array, target, left, right);
        }
    }
}

---

输出 2