LeetCode 209. 长度最小的子数组（二分没写出来滑动窗口写出来了）

ゝ一纸荒年。 2022-10-25 04:48 202阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]

//解法一：前缀和 + 二分
    //https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/qian-zhui-he-er-fen-hua-dong-chuang-kou-by-coldme-/
    class Solution {
        
        public int minSubArrayLen(int s, int[] nums) {
        
            int n = nums.length;
            int[] sum = new int[n + 1];
            for(int i = 1; i <= n;i++)//初始化前缀和数组
                sum[i] = sum[i - 1] + nums[i - 1];
            int ans = Integer.MAX_VALUE;
            //数组起始点固定，二分找终止点
            for(int i = 0; i < n; i++){
        
                int l = 0;
                int r = n - 1;
                int mid;
                while(l < r){
        
                    mid = l + r >> 1;
                    int diff = sum[mid + 1] - sum[i];
                    if(diff >= s)
                        r = mid;
                    else
                        l = mid + 1;
                }
                //找到终止点
                if(sum[l + 1] - sum[i] >= s)
                    ans = Math.min(ans, l - i + 1);
            }
            if(ans == Integer.MAX_VALUE)
                return 0;
            return ans;
        }
    }

//解法二：滑动窗口（自己写出来的）
    class Solution {
        
        public int minSubArrayLen(int s, int[] nums) {
        
            int n = nums.length;
            int l = 0;
            int r = 0;
            int cur = 0;
            int res = n + 1;
            while(r < n){
        
                cur += nums[r];
                r++;
                while(cur >= s){
        
                    res = Math.min(res, r - l);
                    cur -= nums[l];
                    l++;
                }
            }
            if(res == n + 1)
                return 0;
            return res;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/82c0c0dad896430d835e2f9bcecdad90.png