leetcode 209. 长度最小的子数组

一开始的时候还在思考为什么做出来这题时间如此糟糕，

后来发现这个东西真的很慢：

if(Arrays.stream(nums).sum() < target){return 0;}

它基本上用掉了4ms左右的时间，后面把它改成fori求和就快了很多，只需要1ms。

思路：滑动窗口

对于这种情况，我们首先想到的是双指针。

1、暴力解法，对于每个索引开始的子数组进行遍历，效率很差。

2、滑动窗口：

（0）判断总和是否大于target

（1）首先找到一个大于target的窗口，这个过程是右窗口移动；

（2）试图缩小窗口，即将左窗口向右移动；

（3）记录这个最窗口长度，然后将右窗口向右移动一格；

（4）重复2-3，找到最小窗口。

代码：

public static int minSubArrayLen(int target, int[] nums) {
    //（0）的判断
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
    }
    if(sum < target) return 0;
    // 一些变量
    int n = nums.length;
    int minLen = n;
    int len = 0;
    int slow = 0;
    int fast = 0;
    int count = nums[0];
    // （1）
    while (count < target) {
        count += nums[++fast];
    }
    // （2）-（4）
    while(fast < n) {
        while (count - nums[slow] >= target) {
            count -= nums[slow++];
        }
        len = fast - slow + 1;
        minLen = Math.min(len, minLen);
        if(fast + 1 >= n) break;
        count += nums[++fast];
    }
    return minLen;
}

原文地址：https://blog.csdn.net/qq_20411067/article/details/140380073

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！