关于java:LeetCode-209-长度最小的子数组

34次阅读

共计 1095 个字符，预计需要花费 3 分钟才能阅读完成。

题目形容

给定一个含有 n 个正整数的数组和一个正整数 s，找出该数组中满足其和 ≥ s 的长度最小的间断子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输出：s = 7, nums = [2,3,1,2,4,3]
输入：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

进阶：

如果你曾经实现了 O(n) 工夫复杂度的解法, 请尝试 O(n log n) 工夫复杂度的解法。

思路剖析

这里采纳双指针 + 滑动窗口的办法。那么什么是滑动窗口呢？

如图，以 s = 7, nums = [2,3,1,2,4,3]为例，要实现滑动窗口，得有两个指针，头指针 start 指向子数组的第一个元素，尾指针 end 指向子数组最初一个元素。

一开始时，start 与 end 都指向子数组的第一个元素。

当 end 后移一位，咱们就能够求得第一个元素和第二个元素的和。

通过 end 后移，咱们能够累加求得子数组元素的和，当和大于等于给定输出阈值 s 时，end 指针不再后移，就比方图中进行求和的条件就是 2+3+1+2 > 7。此时咱们还要判断这个子数组的长度是不是所有子数组长度中最小的那个，子数组长度能够通过指针的地位来求得，为end-start+1。最初题目要求返回的子数组长度，就是滑动窗口的大小。

滑动窗口的要害在接下来的步骤中，当咱们完结下面这次循环之后应该做什么? 咱们能够将之前求得的子数组之和减去 start 指针地位上的元素值，而后将 start 指针后移，直到满足 s <7 为止。窗口是不是就滑动了？

而后持续让 end 指针后移，周而复始，最初题目要求返回最小子数组长度，就是滑动窗口的最短长度。

示例代码

class Solution {public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if(n == 0){return 0;}
        // end - start + 1 为子数组的元素个数
        int start = 0;      
        int end = 0;
        int sumVal = 0;     // 子数组元素之和
        int minLen = Integer.MAX_VALUE;  // 子数组的最小长度，初始化为 Integer.MAX_VALUE

        while(end < n){sumVal += nums[end];
            while(sumVal >= s){minLen = Math.min(minLen, end - start + 1);
                sumVal -= nums[start];
                start++;
            }
            end++;
        }

        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

复杂度剖析