长度最小的子数组
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 26 ms, 内存: 17.7 MB
/*
* 思路:虽然Java Stream不太适合这种需要双指针滑动窗口的算法,但我们可以用Stream来解决辅助部分。
* 具体的滑动窗口部分仍需要使用传统的循环方式。
*/
import java.util.stream.IntStream;
public class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int minLength = Integer.MAX_VALUE;
int sum = 0;
int start = 0;
for (int end = 0; end < n; end++) {
sum += nums[end];
while (sum >= target) {
minLength = Math.min(minLength, end - start + 1);
sum -= nums[start++];
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
}
解释
方法:
这个题解采用了滑动窗口(双指针)的方法,来寻找数组中的最小连续子数组,其和大于等于给定的target。方法中,我们定义两个指针left和right,表示子数组的左右边界。从头开始遍历数组,逐渐扩展right指针来增加子数组的和。每当子数组的和达到或超过target时,尝试通过移动left指针来缩小窗口大小,直到子数组的和小于target。在此过程中,我们记录达到条件的最小子数组长度。整个过程中,每个元素只会被访问两次(一个添加到窗口,一个从窗口中移除),因此时间效率较高。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
算法为什么在总和达到或超过target时尝试通过缩小左边界来寻找最小长度,而不是继续增加右边界?
▷🦆
在算法中,如果总和刚好等于target,为何仍要尝试移动左指针来缩小窗口?这样做的目的是什么?
▷🦆
当数组中的所有元素之和仍小于target时,算法的返回值为0。在这种情况下,是否有必要遍历完整个数组?
▷