题目描述

给定一个含有 个正整数的数组和一个正整数 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 – 朴素算法O(n^2)

解法1使用朴素算法,我们使用指针i, j(0<=i<=j<|nums|)来描述子数组,然后计算i到j区间元素到和,如果大于等于s则取j – i + 1作为可能到解ans;如果小于s则j右移。
为了实现O(1)时间复杂度的区间求和,我们可以使用prefix sum算法预先计算前缀和。当指针i和j扫描完所有的连续区间,我们取最小的解就是答案。如果找不到子数组当和大于等与s,就返回0。

需要注意一点,当找到一对i, j我们就可以退出内层循环。因为继续找下去的子序列长度已定大于(i-j+1),否则会TLE。算法的时间复杂度为O(n^2),空间复杂度为O(n) (存放前缀和)。全部代码如下:

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int[] prefix = new int[nums.length];
        int ans = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {
            prefix[i] += (i == 0 ? 0:prefix[i - 1]) + nums[i];
        }

        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                if (prefix[j] - prefix[i] + nums[i] >= s) {
                    ans = Math.min(ans, j - i + 1);
                    break;
                }
            }
        }

        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

解法2 – 优化的朴素算法O(nlogn)

我们沿用解法1的思路,但是对寻找连续区间上进行优化。我们让i = [0, |nums|),使用二分搜索寻找j,其中i <= j < |nums|。因为我们有前缀和数组prefix,我们可以在O(logn)的时间内找到一个下界(lower bound),使得prefix[j] – prefix[i] >= s。那么,j – i +1就是其中一个解,当i遍历完整个数组时,就取最小的那个解作为答案。

该解法的时间复杂度为O(nlogn),空间复杂度O(n)。全部代码如下:

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int[] prefix = new int[nums.length];
        int ans = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {
            prefix[i] += (i == 0 ? 0 : prefix[i - 1]) + nums[i];
        }

        for (int i = 0; i < nums.length; i++) {
            int left = i;
            int right = nums.length;

            // find lower bound and break
            while (left < right) {
                int mid = (left + right) >>> 1;

                if (prefix[mid] - prefix[i] + nums[i] >= s) {
                    if (mid == 0 || prefix[mid - 1] - prefix[i] + nums[i] < s) {
                        ans = Math.min(ans, mid - i + 1);
                        break;
                    }
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
        }

        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

解法3 – 滑动窗口O(n)

解法3很巧妙,我们可以使用两个指针left、right描述一个区间(称为窗口)。首先让窗口的前沿指针right移动,统计经过的元素和sum。当sum>=s时,就找到了一个解。然后窗口的后沿指针left移动,将路过的元素从sum中减去,如果减掉后仍然使得sum >= s,这也是一个解。当left与right指针都指向了数组nums都末尾,整个扫描就结束了,我们选取最短解作为答案。

算法的时间复杂度O(n),空间复杂度O(1)。全部代码如下:

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0;

        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= s) {
                ans = Math.min(ans, right - left + 1);
                sum -= nums[left++];
            }
        }

        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

参考:https://leetcode.com/articles/minimum-size-subarray-sum/

Leave a Reply

Your email address will not be published. Required fields are marked *