题目
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
关注公众号哦
网友评论