设计制作一个 个人主页网站,淄博做网站的公司都有哪些,可以做网站的行业,手机微信营销软件209. 长度最小的子数组
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] #xff0c;并返回其长度。如果不存在符合条件的子数组#xff0c;返回 0 …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)) 时间复杂度的解法。
解题方法
C 暴力双循环——超时
int mymin(int a, int b) {if (a b)return b;elsereturn a;
}int minSubArrayLen(int target, int* nums, int numsSize) {int count INT_MAX;if (numsSize 0) {return 0;}for (int i 0; i numsSize; i) {int sum 0;for (int j i; j numsSize; j) {sum sum nums[j];if (sum target) {count mymin(count, j - i 1);break;}}}return count INT_MAX ? 0 : count;
}C 滑动窗口法
int mymin(int a, int b) {if (a b)return b;elsereturn a;
}int minSubArrayLen(int target, int* nums, int numsSize) {int count INT_MAX;int start 0, end 0; // 定义窗口开始、结束int sum 0;if (numsSize 0) {return 0;}while (end numsSize) {sum sum nums[end]; // 求窗口中元素和while (sum target) {count mymin(count, end - start 1); // 求最小窗口sum sum - nums[start]; // 求和start; // 缩小窗口}end; // 增大窗口}return count INT_MAX ? 0 : count;
}复杂度分析 时间复杂度为 O(n)其中 n 是数组的长度。 空间复杂度为 O(1)。
