美文网首页
LeetCode—209—Minimum Size Subarr

LeetCode—209—Minimum Size Subarr

作者: yuandatou | 来源:发表于2018-10-18 10:16 被阅读9次

    题目

    Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
    Example:
    Input: s = 7, nums = [2,3,1,2,4,3]
    Output: 2
    Explanation: the subarray [4,3] has the minimal length under the problem constraint.

    翻译

    给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。返回这个最短的连续子数组长度值,如果不存在符合条件的子数组,返回 0。
    输入: s = 7, nums = [2,3,1,2,4,3]
    输出: 2
    解释: 子数组 [4,3] 是该条件下的长度最小的子数组。

    解题思路

    首先能想到的就是,找出所有的子数组,并计算他们的和,然后判断是否大于等于给定的目标值。并找到长度最小的那个子数组。
    用代码实现如下:

    // 209. Minimum Size Subarray Sum
    // https://leetcode.com/problems/minimum-size-subarray-sum/description/
    //
    // 暴力解法
    // 该方法在 Leetcode 中会超时!
    // 时间复杂度: O(n^3)
    // 空间复杂度: O(1)
    public class Solution1 {
    
        public int minSubArrayLen(int s, int[] nums) {
    
            if(s <= 0 || nums == null)
                throw new IllegalArgumentException("Illigal Arguments");
    
            int res = nums.length + 1;
            for(int l = 0 ; l < nums.length ; l ++)
                for(int r = l ; r < nums.length ; r ++){
                    int sum = 0;
                    for(int i = l ; i <= r ; i ++)
                        sum += nums[i];
                    if(sum >= s)
                        res = Math.min(res, r - l + 1);
                }
    
            if(res == nums.length + 1)
                return 0;
    
            return res;
        }
    }
    
    

    可以看出来这种解法,包含了三重循环。外面两层找到所有子数组,最内层计算当前数组的sum值。时间复杂度为O(n^3),显然不是一种优雅的解法。下面我们来看一种新的解法。俗称滑动窗口。

    优化解法

    1.png

    第一种解法之所以时间复杂度比较高呢,是包含了大量的重复运算。看上面的图。如果我们知道了nums[i...j]的sum值,那么nums[i...j-1]和nums[i...j+1]的sum值就特别容易得到。此时我们假设nums[i...j]连续数组的和小于s。那么此时我们将j指针向右移动一位;


    2.png

    移动到直到nums[i...j]的和大于或者等于s时。此时我们就找到了一个符合条件的连续子数组,我们将他的长度记录下来。


    3.png
    当前sum值大于或者等于s值。因为我们要求最短的子数组。所以此时我们将左指针i向右移动。
    2.png

    直到nums[i...j]的sum值小于s。此时我们又继续向右移动j。继续找到一个连续子数组使他的和是大于等于s的。依次类推。 那么我们整个过程一直保持着一个窗口。这个窗口的长度和位置并不是固定不变的。是被i和j两个索引决定的。这个窗口不断向前滑动。来寻找满足题意的连续子数组。那么这也就是滑动窗口的意思。下面我们来看代码实现。

    // 209. Minimum Size Subarray Sum
    // https://leetcode.com/problems/minimum-size-subarray-sum/description/
    //
    // 滑动窗口的思路
    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    public class Solution3 {
    
        public int minSubArrayLen(int s, int[] nums) {
    
            if(s <= 0 || nums == null)
                throw new IllegalArgumentException("Illigal Arguments");
            // nums[l...r]为我们的滑动窗口
            //因为这个区间是闭区间。初始情况窗口是没有元素的。所以r的值为-1
            int l = 0 , r = -1;
            int sum = 0;
            //这里res是代表最小数组的长度
            //将他初始值设为整个数组长度加一。方便了比较以及判断最终是否找到解。
            int res = nums.length + 1;
    
            while(l < nums.length){   // 窗口的左边界在数组范围内,则循环继续
    
                if(r + 1 < nums.length && sum < s)  //判断r+1是保证数组不越界
                    sum += nums[++r];
                else // r已经到头 或者 sum >= s
                    sum -= nums[l++];
    
                if(sum >= s)
                    res = Math.min(res, r - l + 1);  //因为是闭区间,所以数组的长度为r-l+1
            }
    
            if(res == nums.length + 1)
                return 0;
            return res;
        }
    }
    

    关注我免费下载CSDN

    关注公众号哦

    相关文章

      网友评论

          本文标题:LeetCode—209—Minimum Size Subarr

          本文链接:https://www.haomeiwen.com/subject/kzdqzftx.html