使用 oh-my-zsh

209、长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

示例:

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

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum

题解

理想的最小值为1。

1、前缀和 + 双指针

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int len = nums.length;
        int[] profix = new int[len + 1];
        profix[0] = 0;
        // profix[i] 表示nums[0:i-1]的和
        for (int i = 1;i < len+1;i++) {
            profix[i] += profix[i-1] + nums[i-1];
        }
        // System.out.println("profix = " + Arrays.toString(profix));
        int l = 0,r = 1;
        int min = len + 1;

        while(l < r && r < len + 1) {
            if(profix[r] - profix[l] < s) {
                r++;
            } else {
                if (min > r - l + 1){
                    min = r - l + 1;
                }
                while (l < r && profix[r] - profix[l] >= s) {
                    l++;
                    if (min > r - l + 1){
                        min = r - l + 1;
                    }
                }
            }
        }
        return min == len + 1 ? 0 : min;
    }
}

// 不用前缀和
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/

2、前缀和+二分查找

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1]; 
        // 为了方便计算，令 size = n + 1 
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com