LeetCode209.长度最小的子数组
题目链接:209. 长度最小的子数组 - 力扣(LeetCode)
1.常规解法(会超时)
可以先将数组的所有子数组求出来,计算其中元素的值,判断与目标值的大小关系,代码如下:
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int len = n;
boolean flag = false;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += nums[j];
if (sum >= target) {
flag = true;
len = Math.min(len, j - i + 1);
break;
}
}
}
return flag ? len : 0;
}
在上述代码中,使用了flag来判断是否有符合条件的子数组。
2.滑动窗口
使用该方法的前提是数组中的元素全是大于等于0的,可以使用单调性解题。
先定义两个指针left和right,这两个指针均指向第一个元素;
先让right向右移动,并用sum加上right指向的元素,当sum>=target时,可以求出符合条件的子数组的长度,这时可以让left向右移动,用sum减去left指向的元素,根据单调性,sum会越减越小,当sum<target时,left停止移动,继续上面的操作,当right指向数组外面时,最后的len就是结果。
流程图与代码如下:
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int len = Integer.MAX_VALUE;
int sum = 0;
for (int left = 0, right = 0; right < n; right++) {
sum += nums[right];
while (sum >= target) {
len = Math.min(len, right - left + 1);
sum -= nums[left++];
}
}
return len == Integer.MAX_VALUE ? 0 : len;
}
希望读者给出建议!
原文地址:https://blog.csdn.net/2301_79184547/article/details/142965448
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!