LeetCode209 长度最小的子数组

前言

题目： 209.长度最小的子数组
文档： 代码随想录——长度最小的子数组
编程语言： C++
解题状态： 没有思路，暴力解法都没思路…

思路

注意，子数组指的是连续子数组，不然本题就没有意义了。

代码

方法一： 暴力解法

所谓暴力解题，也要将时间复杂度控制在两个循环以内。

• 时间复杂度： $O(n^2)$
• 空间复杂度： $O(1)$

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int result = INT32_MAX;int sum = 0;int subLength = 0;for (int i = 0; i < nums.size(); i++) {sum = 0;for (int j = i; j < nums.size(); j++) {sum = sum + nums[j];if (sum >= target) {subLength = j - i + 1;result = result < subLength ? result : subLength;}}}if (result == INT32_MAX) result = 0;return result;}
};

方法二： 滑动窗口

所谓滑动窗口就是不断调节子数组的起始位置和终止位置，以得到我们想要的结果。

滑动窗口需要确定以下几点：

• 窗口内的元素是什么？
• 如何移动窗口的起始位置？
• 如何移动窗口的终止位置？

本题的关键在于根据当前子数组内的元素和，不断调整窗口的起始位置，降低时间复杂度。

• 时间复杂度： $O(n)$
• 空间复杂度： $O(1)$

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int result = INT32_MAX;int sum = 0;  // 滑动窗口内元素的和int i = 0;  // 滑动窗口的起点int subLen = 0;  // 子数组的长度for (int j = 0; j < nums.size(); j++) {sum += nums[j];while (sum >= target) {subLen = j - i + 1;result = result < subLen ? result : subLen;sum -= nums[i++];}}if (result == INT32_MAX) result = 0;return result;}
};