每日题解:LeetCode 209. 长度最小的子数组(差一个解法)

题目描述

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

示例：

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

进阶：

如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

解法

JAVA
双指针

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

    }
}

解题思路

双指针

题目有个提升的写法时间复杂度为O(n log n)，这个解法应该前缀和加二分法。由于我对前缀和的使用很差，暂时先把这个解法空着，
先做一个时间复杂度为O(n)的，由于涉及到数组的区域间的和对比，使用双指针就比较好，
首先我们先定义几个遍历

//左右指针，当前的数组和、数组的长度
int start=0,end=0,sum=0,sum=0;len=nums.length;
//这里将答案默认的值设置为=Integer.MAX_VALUE，方便在遍历中进行比较
int ans=Integer.MAX_VALUE;

一般在设置答案的初始化，如果明确规定了返回值的的边界，就设置规定的边界，其他涉及到对比的时候，使用Integer的边界作为初始值，方便进行操作
题目要求找出该数组中满足其和 ≥ s 的长度最小的连续子数组，即进入对比的条件为(sum>=s)，然后将当前的区间的长度和返回值进行对比

ans=Math.min(ans,end-start+1);

那么start和end什么时候进行移动呢？
先考虑start指针的移动，当(sum>=s)满足的时，更新了ans值时，需要往后移动，即我们的左指针和右指针同时移动，移动之后，此时sum就需要变化

  while (sum>=s){
                ans=Math.min(ans,end-start+1);
                //减去左指针的值，同时左指针移动一位
                sum-=nums[start];
                start++;
}

那么右指针呢？
由于我们每次外遍历的时候都需要更新当前的sum值，sum+=nums[end];那么为了保证进入遍历的时候，都能更新值，那么一次遍历结束前，end指针后移一位

 end++;

每一轮迭代，将sum+=nums[end]，如果 (sum>=s，则更新子数组的最小长度ans(Math.min(ans,end-start+1);)，然后start指针往后一位的同时，减去当前的nums[start]，同时每次遍历end指针往后移动一位，直到我们end指针达到数组长度len
这里有个有个地方需要注意，内部是whlie循环，而不是if条件判断，这里主要是左指针在达到条件的继续往右指针靠近，可以寻找到当前最短的长度连续子数组

清水1024