LeetCode.209. 长度最小的子数组

题目

题目链接

分析

本题的题意就是让我们找最短的子数组和 >= target 的子数组的长度。

首先最能想到的就是暴力方法，外层循环以数组每一个元素都作为起点，内存循环累加元素，当大于等于 target 的时候记录当前元素个数，更新最终的值。

我们可以利用双指针 left 、right ，right 遍历当前数组，累加元素和 sum，当发现大于等于 target 的时候，我们就可以缩小 left 和 right 框住的区域，也就是让 left++，sum 减去left 的值，如果sum还是大于等于target，记录left++，如果sum小于 target了，我们就继续让 框住的窗口变大，right++。这个过程一直更新最终的值。

代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int n  = nums.length;
        int res = Integer.MAX_VALUE;
        int sum = 0;
        while(right < n) {
            sum += nums[right];
            while(sum >= target) {
                res = Math.min(res,(right - left + 1));
                sum -= nums[left++];
            }
            right++;
        }
        return res == Integer.MAX_VALUE?0:res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18