天天看點

leetcode----209. Minimum Size Subarray Sum

連結:

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

大意:

給定一個正整數數組nums以及一個正整數s,要求從nums找出最短的連續區間,使得區間内數字的和大于等于s,傳回區間中元素的個數。規定:若找不到這樣的區間,則傳回0.例子:

leetcode----209. Minimum Size Subarray Sum

思路:

記錄兩個指針變量start和curIdx,start表示目前所找區間的左端點,curIdx為周遊到的數組目前位置。以及另外一個變量subSum,記錄區間[start, curIdx)的和。

當有subSum + nums[idx] >= s時,我們應該再滿足subSum + nums[idx] >= s的前提下,盡可能增大start(縮小區間的長度)

最後就是更新區間的最短長度啦。。

代碼:

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        // curIdx為目前周遊到的位置  start為滿足區間的最小左位置 subSum為nums在[start,curIdx)的和
        int min = Integer.MAX_VALUE, curIdx = 0, start = 0, subSum = 0;
        while (curIdx < nums.length) {
            // 如果找到一個curIdx使得[start,curIdx)的和滿足大于等于s 那麼需要盡可能地增大start(縮小區間),同時滿足subSum + nums[curIdx] >= s
            if (subSum + nums[curIdx] >= s) {
                while (subSum + nums[curIdx] >= s) {
                    subSum -= nums[start++];
                }
                min = Math.min(min, curIdx - (start - 1) + 1);
            }
            subSum += nums[curIdx++];
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}
           

結果:

leetcode----209. Minimum Size Subarray Sum

結論:

思維思路很重要。