209-长度最小的子数组
2021-03-12 22:31
标签：递增 tar int vector 双指针 大于等于 array subarray algorithm 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。 示例： 输入：s = 7, nums = [2,3,1,2,4,3] 进阶： 如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。 注意题目中的是连续的子数组，直接办法是遍历，从每个nums[i]出发，找到最短的超过target的值，然后记录最短的长度，代码如下： 时间复杂度O(n^2)，空间复杂度：使用了额外的存储，为O(1) 提交后超时。。。 提示：双指针、二分查找 使用双指针：如果【idx1-idx2】的和超过target，则记录长度，然后向右移动idx1，如果此时还满足，则更新minLen；如果此时不满足了，则当前区间内的值小于target，则向右移动idx2直到满足，实时更新minLen，代码如下： 双指针相当于只遍历了一次，时间复杂度O(n)，空间复杂度O(1) 看解答后，有一种方法为：前缀法+二分查找 原理： sum[i]表示从nums[0]到nums[i]的和，则 sum[i]-sum[j] 表示区间 [ j+1, i] 之间数字的和，然后在查找target时，即：sum[i] - sum[j] >= target ，即：寻找 i 使得： sum[i] >= target+ sum[j] 而输入数组都是正整数，则 sums 数组一定是递增的，可以用二分查找法找到符合的值 代码： 二分查找的时间复杂度：O(lgn)，在循环内嵌套二分查找，时间复杂度为： O(nlgn) 空间复杂度，使用了一个sums数组，O(n) 中有一个函数：lower_bound，用于查找一个递增数组内，大于等于target的最小索引，可用于替换上面的findBound函数 209-长度最小的子数组 标签：递增 tar int vector 双指针 大于等于 array subarray algorithm 原文地址：https://www.cnblogs.com/zyk1113/p/14068769.html题目：
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。解答一
//1-暴力搜索，超时
int minSubArrayLen(int s, vectorint>& nums)
{
int idx1 = 0;
int minLen = INT_MAX;
int sum = 0;
while (idx1 nums.size())
{
sum = nums[idx1];
if (sum >= s)
return 1;
for (int idx2 = idx1 + 1; idx2 )
{
sum += nums[idx2];
if (sum >= s)
{
if (idx2 + 1 - idx1 minLen)
{
minLen = idx2 + 1 - idx1;
break;
}
}
}
idx1++;
}
return minLen == INT_MAX ? 0 : minLen;
}
解答二
/双指针法，如果两个指针的范围内超过s，则右移idx1，如果不满足则右移idx2,
//记录最小的长度
int minSubArrayLen2(int s, vectorint>& nums)
{
int minLen = INT_MAX;
int idx1 = 0, idx2 = 0;
int sum = 0;
while (idx2 nums.size())
{
sum += nums[idx2];
while (sum >= s)
{
if (idx2 - idx1 + 1 minLen)
minLen = idx2 - idx1 + 1;
sum -= nums[idx1];
idx1++;
}
idx2++;
}
return minLen == INT_MAX ? 0 : minLen;
}
解答三
//vec是递增的数组，target是目标值，找到值大于等于target的最小下标
//二分查找
int findBound(vectorint>& vec, int left, int right, int target)
{
int l = left, r = right;
int mid = -1;
while (lr)
{
mid = (l + r) >> 1;
if (vec[mid] >= target)
{
r = mid;
}
else
{
l = mid + 1;
}
}
return vec[l] >= target ? l : -1;
}
int minSubArrayLen3(int s, vectorint>& nums)
{
int ans = INT_MAX;
int length = nums.size();
vectorint> sums(length + 1, 0);
for (int i = 1; i )
{
sums[i] = sums[i - 1] + nums[i-1];
}
//sum = nums[i] + sums[i] - sums[k] > s
for (int i = 1; i )
{
int target = s + sums[i - 1];
int bound = findBound(sums, 0, sums.size() - 1, target);
if (bound != -1)
{
if (bound - i + 1 ans)
ans = bound - i + 1;
}
}
return ans == INT_MAX ? 0 : ans;
}
上一篇：C# 集合排序多属性
下一篇：Java线程加入(join)