209 - Minimum Size Subarray Sum

解法一 - Sliding Window

做法滿直覺的,就是一直擴張 windowEnd,如果發現 windowSum 已經比 s 大,那就開始縮減 window,直到走到 nums 的尾巴。

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int windowSum = 0, windowStart = 0;
        int minWindowSize = numeric_limits<int>::max();

        for(int windowEnd=0; windowEnd<nums.size(); windowEnd++) {
            windowSum += nums[windowEnd];

            while(windowSum >= s) {
                minWindowSize = min(minWindowSize, windowEnd-windowStart+1);
                windowSum -= nums[windowStart];
                windowStart++;
            }
        }

        return minWindowSize == numeric_limits<int>::max() ? 0 : minWindowSize;
    }
};

時間複雜度是 O(n),跑起來的效率如下:

Runtime: 12 ms, faster than 66.67% of C++ online submissions for Minimum Size Subarray Sum. Memory Usage: 9.9 MB, less than 82.35% of C++ online submissions for Minimum Size Subarray Sum.

滿酷的,沒想到還可以用 binary search,先記一下。

results matching ""

    No results matching ""