文章目录
- 0.分析
- 1. 暴力求解【超时】
- 2. 滑动窗口
0.分析
这道题要求的是一个区间 是区间就有【第一个元素】 即起始位置
1. 暴力求解【超时】
这道题是要找一个子区间,使得这个区间的所有数 >= target;
把数组中的每⼀个元素作为一个区间的起始位置,每次往这个区间里加一个数,直到这个区间的数和>=target;将所有元素作为起始位置所得的结果中,找到「最⼩值」即为最短子区间。
class Solution
{
public:
int minSubArrayLen(int target, vector<int> &nums)
{
// 记录结果
int ret = INT_MAX;
int n = nums.size();
for (int start = 0; start < n; start++)
{
int sum = 0;
for (int end = start; end < n; end++)
{
sum += nums[end];
if (sum >= target)
{
ret = min(ret, end - start + 1);
break;
}
}
}
return ret == INT_MAX ? 0 : ret;
}
};
2. 滑动窗口
铺垫
滑动窗口的思想实际上是基于【暴力求解】的优化。一般人/普通人在解这类题时,一般直接想到的解决方案就是【暴力求解】,但是我们都知道,【暴力求解】通常不是一个问题的最优方案。基于【暴力求解】,佬们就总结出来在【暴力求解】基础之上的优化,这个优化对于有“算法”思想的人来说不难想到/理解,关键在于有没有用心思考更优解。
讲解
【暴力求解】中提到,遍历数组,把每一个元素作为【结果区间】的首元素,依次顺序添加直到满足条件,记录将该元素作为【结果区间】首元素下【结果区间】的长度,遍历结束后,在取这些值的最小值即为结果。
现在我们细思【暴力求解】的过程,当把arr[0]作为【结果区间】的首元素时,我们计算求和了一部分值,当下一轮把arr[1]作为【结果区间】的首元素时,我们又重新计算了在第一轮中计算过的值,这就是【暴力求解】效率低下的原因。
学过数据结构我们知道,提升一个算法的时间复杂度,我们可以通过减少语句的执行/循环的次数/递归的次数等。在这道题中,有没有一种方法,使得我们能够减少计算的次数?
解答
第一个区间计算完之后,计算第二个区间时,实际上就是把【该区间首元素的前一个元素】即(遍历的上一个元素)移除,对于移除后的新区间
- 仍有可能满足条件【左端元素可能很小,划出去之后依旧满⾜条件】
- 不满足,即变小了。我们不再从arr[1]开始继续往后添加元素,而是把第一个区间去除arr[0]的剩余元素直接拿过来用,在这个【旧区间】的基础上再添加。
如此大大的减少了计算的次数。
代码
class Solution
{
public:
int minSubArrayLen(int target, vector<int> &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;
}
};