Leetcode 209. Minimum Size Subarray Sum

Description

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Solution

这道题让找到一段连续满足sum >= s的子数组,求最短长度。

连续求最优两个关键字已经表明了这是一道典型的滑动窗口题。

思路1 滑动窗口

定义窗口的左边界left和右边界right,每次循环right自增1,并判断当前窗口的值是否满足条件,满足条件则开始求最优,压缩窗口长度,左边界开始自增。

代码如下:

Java

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        int l = 0, r = 0, sum = 0;
        int res = n;
        for (; r < n; r++) {
            sum += nums[r];
            while (sum >= s) {
                res = Math.min(res, r - l + 1);
                sum -= nums[l++];
            }
        }
        if (l == 0 && sum < s) return 0;
        return res;
    }
}

Python

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        res = n = len(nums)
        l = total = 0
        for r in range(n):
            total += nums[r]
            while total >= s:
                res = min(res, r - l + 1)
                total -= nums[l]
                l += 1
        if l == 0 and total < s:
            return 0
        return res

思路2 二分法

时间复杂度:O(nlogn)。判断是否存在一个大小为k的窗口满足条件

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int i = 1, j = nums.length, min = 0;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (windowExist(mid, nums, s)) {
                j = mid - 1;
                min = mid;
            } else i = mid + 1;
        }
        return min;
    }


    private boolean windowExist(int size, int[] nums, int s) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i >= size) sum -= nums[i - size];
            sum += nums[i];
            if (sum >= s) return true;
        }
        return false;
    }
}

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号