力扣刷题记录四：209、长度最小的子数组

记录力扣刷题第四题：

本文中包含C++两种方法的题解以及Java和Python的题解

题目描述如下

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

来源：LeetCode

思路：还是老样子，一看这题目就想到了双for循环，咔咔一写，果然过了，废话不多说了，直接上代码：

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

时间复杂度为O(n^2)
这里面有一些小细节要注意，比如Min赋的初始值不能小于数组长度，否则当target等于数组元素之和时就会出现错误。还有就是返回时要注意判断数组中所有元素加一起都不能等于target的情况。

但是总不能一直靠双for循环写题呀，又丑时间复杂度又高，得找办法优化优化。这里介绍滑动窗口法(LeetCode运行时间最少的那个没太看懂)。滑动窗口法和双指针法很相似，用一个指针指向窗口的起始位置，另一个指针指向窗口的结束位置。首先需要遍历数组，得到第一个满足sum>=target的子数组，此时画出第一个满足条件的窗口。接着，将窗口起始位置后移(sum-num[i];i++)，若sum>=target仍然成立，就继续将起始位置前移，直到sumclass Solution { public: int minSubArrayLen(int target, vector& nums) { //窗口后移步骤 int n = nums.size(); int sum = 0, cnt = 0; int Min = n + 1, i = 0; for(int j = 0; j < n; ++j) { sum += nums[j]; while(sum >= target) { cnt = j - i + 1; Min = cnt < Min ? cnt: Min; //下面两行为窗口前移步骤 sum -= nums[i]; ++i; } } return Min == n + 1 ? 0 : Min; } };

下面放上Java和Python用窗口滑动法的做法： Java

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int sum = 0, cnt = 0;
        int Min = n + 1, i = 0;
        for(int j = 0; j < n; ++j) {
            sum += nums[j];
            while(sum >= target) {
                cnt = j - i + 1;
                Min = cnt < Min ? cnt : Min;
                sum -= nums[i];
                ++i;
            }
        }
        return Min == n + 1 ? 0 : Min;
    }
}

感觉写起来跟C++一模一样，哈哈哈。

Python

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    	n = len(nums)
    	Sum, cnt = 0, 0
    	Min = n + 1
    	i = 0
    	for j in range(0, n):
    		sum += nums[j]
    		while sum >= target:
    			cnt = j - i + 1
    			Min = min(Min, cnt)
    			sum -= nums[i]
    			i += 1
    	return 0 if Min == n + 1 else Min

力扣刷题记录四：209、长度最小的子数组

C/C++/C#相关栏目本月热门文章