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;
    }
};

原文地址：https://blog.csdn.net/daishabby2486/article/details/140664110

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！