LeetCode209. 长度最小的子数组🌟🌟🌟🌟中等
问题描述
原文链接：209. 长度最小的子数组
给定一个含有 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 <= 1091 <= nums.length <= 1051 <= nums[i] <= 105
思路讲解
这道题我们可以用两个for循环来暴力求解，外循环每次固定一个元素，然后内循环来计算以这个元素为开头的连续子数组，这样子我们可以计算机所有 子数组和 >= target 的所有子数组，然后取最小的那个子数组就可以了。
但是这种方法的时间复杂度是 O(n^2)，我们其实 可以继续优化，事实上，内循环计算子数组和的时候，我们是不需要每次都从头元素遍历计算子数组的和的，比如当子数组[l1, …,r1] 的和 sum 满足 sum >= target 的时候，如果此时我们要继续寻找新的子数组，那么我们就会让元素 nums[l1+1] 作为新的头元素，此时我们可以很容易得出子数组[l1-1,…,r1] 的和是 sum – nums[l1+1]。
之后我们在判断 sum – nums[l1+1] 是否 >= target，如果满足，则找到新的子数组[l1-1,…,r1]，继续按照这种方式移动；如果 sum- nums[l1+1] < target，那么我们需要扩大子数组长度，也就是把 nums[r1+1] 也加进来。
按照这种方式，我们在 O(n) 的时间复杂度内，就可以找到最小的子数组。文字可能不大好描述，具体还是看视频哈。
代码实现
Java
public int minSubArrayLen(int target, int[] nums) {
if(nums == null || nums.length < 1){
return 0;
}
int l = 0, r = 0;
int len = Integer.MAX_VALUE;
int sum = 0;
while(r < nums.length){
sum += nums[r];
while(sum >= target){
len = Integer.min(len, r - l + 1);
sum -= nums[l];
l++;
}
r++;
}
return len == Integer.MAX_VALUE ? 0 : len;
}
Python
class Solution(object):
def minSubArrayLen(self, target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int
"""
if nums is None or len(nums) < 1:
return 0
l, r = 0, 0
length = float("inf")
s = 0
while r < len(nums):
s += nums[r]
while s >= target:
length = min(length, r - l + 1)
s -= nums[l]
l += 1
r += 1
return length if length != float("inf") else 0
C++
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
if(nums.empty()) {
return 0;
}
int l = 0, r = 0;
int len = INT_MAX;
int sum = 0;
while(r < nums.size()){
sum += nums[r];
while(sum >= target){
len = min(len, r - l + 1);
sum -= nums[l];
l++;
}
r++;
}
return len == INT_MAX ? 0 : len;
}
};
Go
func minSubArrayLen(target int, nums []int) int {
if nums == nil || len(nums) < 1 {
return 0
}
l, r := 0, 0
length := math.MaxInt32
sum := 0
for r < len(nums) {
sum += nums[r]
for sum >= target {
length = min(length, r - l + 1)
sum -= nums[l]
l++
}
r++
}
if length == math.MaxInt32 {
return 0
}
return length
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
评论(9)
class Solution {& nums) {
public:
int minSubArrayLen(int target, vector
int i=0;
int sum=0;//元素和
int res=INT32_MAX;//最终子数组的长度，找最小用MAX，找最大用MIN
int subLength=0;//暂时存储子数组的长度，用来和res比较，以更新res
//左边界初始为0，右边移动，找sum刚刚≥target的位置
for(int j=0;j<nums.size();j++){
sum+=nums[j];
//找到右边界，调整左边界，看看可不可以更短
while(sum>=target){
subLength=j-i+1;
res=(subLength<res)?subLength:res;
sum-=nums[i++];
}
}
//只要res被改过，就返回res
return resINT32_MAX?0:res;
}
};
1、首先，确定左边界i，左边界为0，然后找右边界j，再不断调整左边界
2、先找满足条件的子数组，再判定是不是长度最小
3、先写思路，再写代码，写不出代码，是因为没想明白
4、先写主体的功能，后面再定义变量；写出来再优化
5、找最小值，初始化用INT32_MAX，找最大值，初始化用INT32_MIN
day 2 打卡
暴力法：
思路：用两个for循环，外循环每次固定一个元素，然后内循环来计算以这个元素为开头的连续子数组（子数组和 >= target ），取最小的那个子数组即可
Time：O(n^2)
Space：O(1)
滑动窗口：
思路：累计求和。不需要每次从头遍历计算数组的和，维护一个左右指针，不断移动右指针，更新窗口内的和，当和大于等于target时，继续寻找新的子数组，尝试缩小左指针，直到无法满足条件为止。
Time：O(n)
Space：O(1)
滑动窗口，注意里面移动左边界时是while
打卡