学校局域网站建设,无锡网站建设专业极速信息,凭祥网站建设,寰宇seo每日一题(LeetCode)----数组–长度最小的子数组
1.题目#xff08; 209.长度最小的子数组#xff09;
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] …每日一题(LeetCode)----数组–长度最小的子数组
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
进阶
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
2.解题思路
思路一 暴力法
暴力法是最直观的方法。初始化子数组的最小长度为无穷大枚举数组 nums 中的每个下标作为子数组的开始下标对于每个开始下标 iii需要找到大于或等于 iii 的最小下标 j使得从 nums[i] 到 nums[j] 的元素和大于或等于 s并更新子数组的最小长度此时子数组的长度是 j−i1j-i1j−i1。
原作者力扣官方题解
链接https://leetcode.cn/problems/backspace-string-compare/
方法二前缀和 二分查找
方法二的时间复杂度是 O(n2)因为在确定每个子数组的开始下标后找到长度最小的子数组需要 O(n) 的时间。如果使用二分查找则可以将时间优化到 O(logn)
为了使用二分查找需要额外创建一个数组 sums 用于存储数组 nums 的前缀和其中 sums[i]\text{sums}[i]sums[i] 表示从 nums[0] 到 nums[i−1]的元素和。得到前缀和之后对于每个开始下标 iii可通过二分查找得到大于或等于 iii 的最小下标 bound使得 sums[bound]−sums[i−1]≥s并更新子数组的最小长度此时子数组的长度是 bound−(i−1)。
因为这道题保证了数组中每个元素都为正所以前缀和一定是递增的这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正这里就不能使用二分来查找这个位置了。
这里最开始没有看懂看了力扣上这位网友的评论明白了很多
原作者力扣官方题解
链接https://leetcode.cn/problems/backspace-string-compare/ 思路三 滑动窗口
其实滑动窗口就是双指针我们定义两个指针分别表示滑动窗口的起始位置和结束位置滑动窗口就是子数组以此我们就可以求出子数组的总和看是否符合条件了
初始时滑动窗口的起始位置和结束位置都是数组的首元素然后我们向右移动滑动窗口的结束位置相当于是向右遍历一遍数组每向右移动一位我们都看一下滑动窗口的总和是否大于等于目标值如果大于我们就计算一下当前子数组长度然后更新一下答案之后让滑动窗口的起始位置向后移动一位直到滑动窗口的总和下于目标值了我们继续向右遍历直到遍历结束得到最终的答案
3.写出代码
思路一的代码
class Solution {
public:int minSubArrayLen(int s, vectorint nums) {int n nums.size();if (n 0) {return 0;}int ans INT_MAX;for (int i 0; i n; i) {int sum 0;for (int j i; j n; j) {sum nums[j];if (sum s) {ans min(ans, j - i 1);break;}}}return ans INT_MAX ? 0 : ans;}
};
原作者力扣官方题解
链接https://leetcode.cn/problems/backspace-string-compare/
思路二的代码
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int lengthnums.size();vectorint sum(length1,0);int ans0x7fffffff;//得到前缀和for(int i1;ilength;i){sum[i]sum[i-1]nums[i-1];}//遍历得到答案for(int i1;ilength;i){int temptargetsum[i-1];int boundlower_bound(sum.begin(),sum.end(),temp)-sum.begin();//注意lower_bound函数的返回值是第一个大于等于目标值的地址所以我们这里减去首元素的地址就可以获得第一个大于等于目标值的下标了if(boundlength1){ansmin(ans,bound-(i-1));}}if(ans0x7fffffff){return 0;}else{return ans;}}
};思路三的代码
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int lengthnums.size();int i0;int sum0;int result0x7fffffff;for(int j0;jlength;j){sumnums[j];while(sumtarget){resultmin(result,j-i1);sum-nums[i];i;}}if(result0x7fffffff){return 0;}else{return result;}}
};
