Leetcode 209 - Minimum Size Subarray Sum

題目

Problem#

給你一個正整數陣列 nums 和一個正整數 target，要求 subarray 總和不超過 target ，要你回傳 subarray 最小的長度，如果找不到則回傳 0

測資限制#

• $1 \le target \le 10^9$
• $1 \le nums \le 10^5$
• $1 \le nums[i] \le 10^4$$

想法#

求 subarray 總和，雙指標

能往右就盡量往右，直到 sum >= target 開始縮減左界（往右長）直到 sum < target 又開始增長右界
每次移動 左界（i）、右界（j） 時去看有沒有 sum >= target 有的話找最小的 j-i+1

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(1)$

AC Code#

Copy

class Solution {
public:
    int minSubArrayLen(int t, vector<int>& v)
    {
        int n = v.size();
        int i = 0, j = 0;
        int sum = 0;
        int ans = INT_MAX;
 
        auto check = [&]() {
            if(sum >= t)
                ans = min(ans, j-i+1);
        };
 
        while(j < n)
        {
            sum += v[j];
 
            check();
 
            while(sum-v[i] >= t)
            {
                sum -= v[i++];
                check();
            }
 
            j++;
        }
        j--;
 
        check();
        return ans == INT_MAX ? 0 : ans;
    }
};

view raw leetcode/209.cpp delivered with ❤ by emgithub

TODO: O(nlogn) 解法