大家好,我是开车的阿Q,自动驾驶的时代已经到来,没时间解释了,快和阿Q一起上车。作为自动驾驶系统工程师,必须要有最好的C++基础,让我们来一起刷题吧。
题目:找到满足条件的最短连续牛群的长度。
题目考察的知识点:
- 数组遍历
- 滑动窗口
题目解答方法的文字分析:
我们可以使用滑动窗口的方法来解决这个问题。滑动窗口是一种技巧,它可以在数组中找到满足特定条件的连续子数组或子序列。我们可以用两个指针 left 和 right 来表示滑动窗口的左右边界,然后移动窗口来寻找满足条件的子数组。
首先,我们初始化 left 和 right 指针都指向数组的第一个元素,然后我们通过不断移动 right 指针来扩展窗口,直到窗口内的元素和大于等于给定的目标战斗力值 target 为止。然后,我们再通过不断移动 left 指针来缩小窗口,直到窗口内的元素和小于 target 为止。在这个过程中,我们可以不断更新最短连续牛群的长度。
在移动窗口时,我们需要注意边界条件,即确保窗口不会超出数组的范围。
举个例子来说明:
假设我们有一个数组 nums = [4, 2, 1, 7, 5],目标战斗力值 target = 8。一开始,left 和 right 都指向第一个元素 4,窗口内的和为 4。然后我们移动 right 指针,使得窗口包含了 4 和 2,窗口内的和为 6。然后再移动 right 指针,使得窗口包含了 4、2 和 1,窗口内的和为 7。此时窗口内的和小于目标值,我们继续移动 right 指针,使得窗口包含了 4、2、1 和 7,窗口内的和为 14。窗口内的和大于目标值,我们记录此时的窗口长度为 4。接下来,我们移动 left 指针,使得窗口内的和变为 10,仍然大于目标值。我们继续移动 left 指针,使得窗口内的和变为 8,恰好等于目标值。此时窗口的长度为 2,比之前记录的长度 4 更短。我们更新记录,并继续移动 left 指针。最后,窗口内的和又变为 6,小于目标值,窗口不再满足条件,我们停止移动,并返回最短窗口长度 2。
本题解析所用的编程语言:C++
完整且正确的编程代码(注释清晰完整):
class Solution { public: int findMinSubarrayLength(int target, vector<int>& nums) { int n = nums.size(); int left = 0; // 窗口的左边界 int sum = 0; // 窗口内元素的和 int minLen = INT_MAX; // 最短窗口长度,初始化为无穷大 for (int right = 0; right < n; ++right) { sum += nums[right]; // 扩展窗口,右边界向右移动 while (sum >= target) { minLen = min(minLen, right - left + 1); // 更新最短窗口长度 sum -= nums[left]; // 缩小窗口,左边界向右移动 ++left; } } return minLen == INT_MAX ? 0 : minLen; } };