MENU

LeetCode209. Minimum Size Subarray Sum(滑动窗口)

2019 年 02 月 05 日 • 阅读: 1167 • LeetCode阅读设置

LeetCode209. Minimum Size Subarray Sum(数组 / 滑动窗口 / 双指针)

  • Medium
  • Accepted:158,657
  • Submissions:466,000

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).


链接

https://leetcode.com/problems/minimum-size-subarray-sum/

题意

给定一个包含n个正整数的数组和一个正整数s,找到一个最小长度的且和大于s的子数组,返回其长度,如果不存在,返回0。

类似的题有,LeetCode3. Longest Substring Without Repeating Characters(滑动窗口)

题解

  • 暴力解法,两层循环找出所有的子数组,一层循环统计和与长度并更新答案,时间复杂度$O(n^3)$
  • 滑动指针,对暴力解法进行优化,实际上我们在计算sum[i, ..., j]时,其中sum[i, ..., j-1]的和已经计算过,我们做了很多次重复计算。其实对于2 3 1 2 4 3,当对于某个子数组符合要求时,再往后面加是没有必要的,此时数组只会更长。
  • 现用两个指针l初始时指向0,r初始时指向-1,其中nums[l, r]表示滑动窗口,用sum来表示[l, r]之间的和,cnt记录长度,那么当$sum<s$时我们就要把r指针右移,否则我们让l指针右移,在循环的过程中如果出现$sum>=s$那么就更新长度cnt,直至循环结束。时间复杂度$O(n)$
  • 一个更优雅的暴力,两层循环找出所有的子数组后,无需再编译一次来求和,我们可以使用前缀和来做预处理,求和的操作为$O(1)$,时间复杂度$O(n^2)$,LeetCode上可以通过
  • 还有一个优化,针对第二重循环,用来查找以索引i开头的符合条件的子数组,但是我们把这个过程减至O(lgn),sums[j] - sums[i] + nums[i] >= s,就是sums[i] >= s + sums[i-1],实际上就是在sums数组中找一个数sums[i]大于等于s + sums[i-1],可以通过二分查找完成,简单一点可以使用STL的lower_bound(),时间复杂度$O(nlogn)$

代码

  • Runtime: 8 ms, faster than 98.57% of C++ online submissions for Minimum Size Subarray Sum.
  • Memory Usage: 2.1 MB, less than 60.66% of C++ online submissions for Minimum Size Subarray Sum.
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int len = nums.size();
        // nums[l...r]为滑动窗口
        int l = 0, r = -1, sum = 0, cnt = len + 1; 
        while (l < len)
        {
            if (r + 1 < len && sum < s)
                sum += nums[++r];
            else
                sum -= nums[l++];
            if (sum >= s)
                cnt = min(cnt, r - l + 1);
        }
        if (cnt == len + 1)
            return 0;
        return cnt;
    }
};

// 如果滑动窗口为[l, r)左闭右开,那么:

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int len = nums.size();
        // nums[l...r)为滑动窗口
        int l = 0, r = 0, sum = 0, cnt = len + 1;
        while (l < len && r < len + 1)
        {
            if (sum < s && r < len)
                sum += nums[r++];
            else
                sum -= nums[l++];
            if (sum >= s)
                cnt = min(cnt, r - l);
        }
        if (cnt == len + 1)
            return 0;
        return cnt;
    }
};
  • Runtime: 140 ms, faster than 12.29% of C++ online submissions for Minimum Size Subarray Sum.
  • Memory Usage: 2.1 MB, less than 84.89% of C++ online submissions for Minimum Size Subarray Sum.
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
            return 0;
        int ans = INT_MAX;
        vector <int> sums(n);
        // 前缀和预处理
        sums[0] = nums[0];
        for (int i = 1; i < n; ++i)
            sums[i] = sums[i-1] + nums[i];
        // 双层循环找到所有的子数组
        for (int i = 0; i < n; ++i)
        {
            for (int j = i; j < n; ++j)
            {
                int sum = sums[j] - sums[i] + nums[i];
                if (sum >= s) // 最短长度,符合要求就可以停止
                {
                    ans = min(ans, (j - i + 1)); 
                    break;
                }
            }
        }
        if (ans == INT_MAX)
            return 0;
        return ans;
    }
};
  • Runtime: 7 ms, faster than 84.65% of C++ online submissions for Minimum Size Subarray Sum.
  • Memory Usage: 10.4 MB, less than 92.63% of C++ online submissions for Minimum Size Subarray Sum.
class Solution {
private:
    int n;
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        n = nums.size();
        int l = 0, r = 0, sum = 0, ans = n + 1;
        while (r < n)
        {
            sum += nums[r++];
            while (sum >= target)
            {
                ans = min(ans, r - l);
                sum -= nums[l++];
            }
            // cout << l << " " << r << " " << sum << " " << ans << endl;
        }
        return ans == n + 1 ? 0 : ans;
    }
};
最后编辑于: 2022 年 03 月 24 日