剑指 Offer II 008. 和大于等于 target 的最短子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

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

输入：target = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

解法

同向双指针（滑动窗口）：
1、难点：当找到值时，左指针要不断靠近右指针去判断这中间是否还有满足条件的结果
2、易错点：需要找一一个长度记录值，这个长度的记录值要适用题目

数组类算法总结

class Solution {
    // 使用同向双指针
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int minLength = nums.length+1;
        for(int right = 0; right<nums.length; right++){
            // 这里是右指针一直加就好了，左指针还用不到
            sum += nums[right];
            // 当右指针到一定位置的时候，左指针需要不断去靠近右指针，看在这个区间有没有值小
            // 条件1：首先左指针必须小于等于右指针
            // 条件2：和必须已经大于了目标值，否则左指针向右推进没有意义
            while(left <= right && sum >= target){
                minLength=Math.min(minLength, right-left+1); 
                sum -= nums[left]; 
                left++;
            }    
        }
        // 判断返回结果有没有改变
        return minLength==nums.length+1 ? 0:minLength;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21