企业营销型网站做的好,php网站开发有前景吗,WordPress后端API,ajax 效果网站目录 1.题目
1.解法⼀#xff08;暴⼒求解#xff09;#xff08;会超时#xff09;#xff1a; 2.解法⼆#xff08;滑动窗⼝#xff09;#xff1a;
1.算法思路#xff1a;
2.手撕图解
3.代码实现 1.C
2.C语言 1.题目
209. 长度最小的子数组
给定一个含有 n…
目录 1.题目
1.解法⼀暴⼒求解会超时 2.解法⼆滑动窗⼝
1.算法思路
2.手撕图解
3.代码实现 1.C
2.C语言 1.题目
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续
子数组 [numsl, numsl1, ..., 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
1.解法⼀暴⼒求解会超时
算法思路 「从前往后」枚举数组中的任意⼀个元素把它当成起始位置。然后从这个「起始位置」开始然 后寻找⼀段最短的区间使得这段区间的和「⼤于等于」⽬标值。 将所有元素作为起始位置所得的结果中找到「最⼩值」即可。
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {// 记录结果int ret INT_MAX;int n nums.size();// 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]// 由于是取到最⼩因此枚举的过程中要尽量让数组的⻓度最⼩// 枚举开始位置for (int start 0; start n; start) {int sum 0; // 记录从这个位置开始的连续数组的和// 寻找结束位置for (int end start; end n; end) {sum nums[end]; // 将当前位置加上if (sum target) // 当这段区间内的和满⾜条件时{// 更新结果start 开头的最短区间已经找到ret min(ret, end - start 1);break;}}}// 返回最后结果return ret INT_MAX ? 0 : ret;}
}; 2.解法⼆滑动窗⼝ 1.算法思路 由于此问题分析的对象是「⼀段连续的区间」因此可以考虑「滑动窗⼝」的思想来解决这道题。 让滑动窗⼝满⾜从 i 位置开始窗⼝内所有元素的和⼩于target那么当窗⼝内元素之和 第⼀次⼤于等于⽬标值的时候就是 i 位置开始满⾜条件的最⼩⻓度。 做法将右端元素划⼊窗⼝中统计出此时窗⼝内元素的和 ▪ 如果窗⼝内元素之和⼤于等于 target 更新结果并且将左端元素划出去的同时继续判 断是否满⾜条件并更新结果因为左端元素可能很⼩划出去之后依旧满⾜条件 ▪ 如果窗⼝内元素之和不满⾜条件 right 另下⼀个元素进⼊窗⼝。 相信科学这也是很多题解以及帖⼦没告诉你的事情只给你说怎么做没给你解释为什么这么 做
为何滑动窗⼝可以解决问题并且时间复杂度更低 ▪ 这个窗⼝寻找的是以当前窗⼝最左侧元素记为 left1 为基准符合条件的情况。也 就是在这道题中从 left1 开始满⾜区间和 sum target 时的最右侧记为right1 能到哪⾥。 ▪ 我们既然已经找到从 left1 开始的最优的区间那么就可以⼤胆舍去 left1 。但是如 果继续像⽅法⼀⼀样重新开始统计第⼆个元素 left2 往后的和势必会有⼤量重复 的计算因为我们在求第⼀段区间的时候已经算出很多元素的和了这些和是可以在计算 下次区间和的时候⽤上的。 ▪ 此时 rigth1 的作⽤就体现出来了我们只需将 left1 这个值从 sum 中剔除。从right1 这个元素开始往后找满⾜eft2 元素的区间此时right1也有可能是满⾜的因为 left1 可能很⼩。 sum 剔除掉left1 之后依旧满⾜⼤于等于target 。这样我们就能省掉⼤量重复的计算。 ▪ 这样我们不仅能解决问题⽽且效率也会⼤⼤提升。时间复杂度虽然代码是两层循环但是我们的 left 指针和right 指针都是不回退的两者 最多都往后移动 n 次。因此时间复杂度是O(N) 。
2.手撕图解 3.代码实现
INT_MAX是C语言中的一个宏定义表示整型数据类型int的最大值。在32位系统中它的值为2147483647在64位系统中它的值为9223372036854775807。这个值可以用来进行数据类型转换、判断数据是否越界等操作。 1.C
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int n nums.size(), sum 0, len INT_MAX;for (int left 0, right 0; right n; right) {sum nums[right]; // 进窗⼝while (sum target) // 判断{len min(len, right - left 1); // 更新结果sum - nums[left]; // 出窗⼝}}return len INT_MAX ? 0 : len;}
}; 2.C语言
int minSubArrayLen(int target, int* nums, int numsSize)
{int sum 0, len INT_MAX;for (int left 0, right 0; right numsSize; right) {sum nums[right]; // 进窗⼝while (sum target) // 判断{len len right - left 1 ? len : right - left 1; // 更新结果sum - nums[left]; // 出窗⼝}}return len INT_MAX ? 0 : len;
}
