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

Author Avatar
清水雅然君 06月 28,2020

题目地址

题目描述

给定一个含有 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条件判断,这里主要是左指针在达到条件的继续往右指针靠近,可以寻找到当前最短的长度连续子数组