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
}