526互联

LeetCode-Java题解 209. Minimum Size Subarray Sum

发布时间 2023-09-15 22:55:25作者: 古宇

题目地址：209. Minimum Size Subarray Sum
解题思路：
    看到这道题，心里本身是有双指针这个概念的，但是不知道怎么用，脑子里第一反应就是暴力解法，双for一把梭，然后时间就超时了...看了题解才知道滑动窗口这个解法，不禁直呼妙啊！感觉和双指针非常类似，其核心点在于避免了暴力算法的枚举，一位一位的从头加到尾计算一遍。就好像有一个滑动窗口，这个窗口只聚焦大于target的子序列，每当大于等于target的时候，滑动窗口定格，记录下子序列长度，然后开启另一个循环，减少元素，直到子序列达到继续增加的条件（子序列长度小于target）。这个序列就好像一个队列一样，出队几个元素，减小队列的长度，再入队几个元素去触摸target的临界值，一旦出队的数量大于入队的元素数量，那么这个子序列的最小长度就会进一步缩小，借此减小子序列的长度。同样是双重循环，这个循环的次数是远小于暴力破解算法的。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
       int length = nums.length;
        if (length <= 0) {
            return 0;
        }
        int subArrayLength = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        int sum = 0;
        while (end < nums.length) {
            sum += nums[end];
            while (sum >= target) {
                subArrayLength = Math.min(subArrayLength, end - start + 1);
                sum -= nums[start++];
            }
            end++;
        }
        return subArrayLength == Integer.MAX_VALUE ? 0 : subArrayLength;
    }
}