长沙哪里有创建网站的公司,公众号怎么赚钱,做网站怎么保证商品是正品,广州微信网站制作力扣题目链接
1. 暴力解法
这道题的暴力解法是两层嵌套for循环#xff0c;第一层循环从 i 0 开始遍历至数组末尾#xff0c;第二层循环从 j i 开始遍历至找到总和大于等于 target 的连续子数组#xff0c;并将该连续子数组的长度与之前找到的子数组长度相比较#xff0…力扣题目链接
1. 暴力解法
这道题的暴力解法是两层嵌套for循环第一层循环从 i 0 开始遍历至数组末尾第二层循环从 j i 开始遍历至找到总和大于等于 target 的连续子数组并将该连续子数组的长度与之前找到的子数组长度相比较若这个子数组长度更短则更新结果。并将初始长度设置为 INT32_MAX 或 nums.size() 1用于判断是否不存在符合条件的子数组通过判断结果是否被赋值若未被赋值就返回0说明没有符合条件的子序列。
//时间复杂度O(n^2)
//空间复杂度O(1)
class Solution {
public:int minSubArrayLen(int s, vectorint nums) {int result INT32_MAX; // 最终的结果int sum 0; // 子序列的数值之和int subLength 0; // 子序列的长度for (int i 0; i nums.size(); i) { // 设置子序列起点为isum 0;for (int j i; j nums.size(); j) { // 设置子序列终止位置为jsum nums[j];if (sum s) { // 一旦发现子序列和超过了s更新resultsubLength j - i 1; // 取子序列的长度result result subLength ? result : subLength;break; // 因为我们是找符合条件最短的子序列所以一旦符合条件就break}}}// 如果result没有被赋值的话就返回0说明没有符合条件的子序列return result INT32_MAX ? 0 : result;}
};2. 滑动窗口
上述暴力解法提交会超时。 所谓滑动窗口就是不断的调节子序列的起始位置和终止位置从而得出我们要想的结果。 在暴力解法中是一个for循环滑动窗口的起始位置一个for循环为滑动窗口的终止位置用两个for循环 完成了一个不断搜索区间的过程。滑动窗口只用一个for循环来完成这个操作。
而这个循环的索引一定是表示 滑动窗口的终止位置。
下面是代码随想录中给出的运用滑动窗口解决问题的过程非常的简洁明了
窗口的结束位置 j 就是遍历数组的指针也就是for循环里的索引。i 则代表窗口的起始位置。
窗口的结束位置 j 首先不断右移并执行 sum nums[j] 计算当前从指针 i 到 j 的子数组之和。当sum target时此时得到一个总和大于等于 target 的连续子数组其长度为count j - i 1此时需判断该长度是否比已记录的最短长度要小若小于则更新最短长度。随后窗口的起始指针 i 开始左移缩小窗口长度注意可能存在左移后其子数组总和仍大于等于 target 的情况所以此处判断应该是 while 而不是 for还需要将 i 原来指向的数值在 sum 中减掉。窗口的起始指针 i 左移至窗口中的子数组不满足条件时此时需要结束指针 j 开始右移直至窗口中的子数组再次满足条件即跳转至第1步当 j nums.size() 时表示数组内全部可能的子数组遍历完成返回结果。最后同样通过将初始长度设置为 INT32_MAX 或 nums.size() 1判断是否不存在符合条件的子数组通过判断结果是否被赋值若未被赋值就返回0说明没有符合条件的子序列。
//时间复杂度O(n)
//空间复杂度O(1)
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int ans nums.size() 1;int sum 0;for(int i 0, j 0; j nums.size(); j){sum nums[j];//注意这里使用while每次更新 i起始位置并不断比较子序列是否符合条件while(sum target){int count j - i 1; //取子序列的长度if(count ans){ans count;}//ans ans count ? ans : count;//这里体现出滑动窗口的精髓之处不断变更i子序列的起始位置sum - nums[i];i;}}//如果ans没有被赋值的话就返回0说明没有符合条件的子序列if(ans nums.size() 1) return 0;else return ans;//return ans (nums.size() 1) ? 0 : ans;}
};关于时间复杂度不要以为for里放一个while就以为是O(n^2) 主要是看每一个元素被操作的次数每个元素在滑动窗后进来操作一次出去操作一次每个元素都是被操作两次所以时间复杂度是 2 × n 也就是O(n)。
