7、长度最小的子数组

题目描述

长度最小的子数组

我们下面再看一种新类型的双指针，也就是我们大家熟知的滑动窗口。这也是我们做题时经常用到的，下面我们来看一下题目吧！

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

题目解析

滑动窗口：就是通过不断调节子数组的起始位置和终止位置，进而得到我们想要的结果，滑动窗口也是双指针的一种。

下面我们来看一下这道题目的做题思路，其实原理也很简单，我们创建两个指针，一个指针负责在前面探路，并不断累加遍历过的元素的值，当和大于等于我们的目标值时，后指针开始进行移动，判断去除当前值时，是否仍能满足我们的要求，直到不满足时后指针 停止，前面指针继续移动，直到遍历结束。是不是很简单呀。前指针和后指针之间的元素个数就是我们的滑动窗口的窗口大小。见下图

好啦，该题的解题思路我们已经了解啦，下面我们看一下，代码的运行过程吧。

题目代码

Java Code:

class Solution {
    public int minSubArrayLen(int s, int[] nums) {

        int len = nums.length;
        int windowlen = Integer.MAX_VALUE;
        int i = 0;
        int sum = 0;
        for (int j = 0; j < len; ++j) {
            sum += nums[j];
            while (sum >= s) {
                windowlen = Math.min (windowlen, j - i + 1);
                sum -= nums[i];
                i++;
            }
        }
        return windowlen == Integer.MAX_VALUE ? 0 : windowlen;

    }
}

C++ Code:

class Solution {
public:
    int minSubArrayLen(int t, vector<int>& nums) {
		int n = nums.size();
      	int i = 0, sum = 0, winlen = INT_MAX;
      	for(int j = 0; j < n; ++j){
          sum += nums[j];
          while(sum >= t){
            winlen = min(winlen, j - i + 1);
            sum -= nums[i++];
          }
        }
      return winlen == INT_MAX? 0: winlen;
    }
};

Python3 Code:

from typing import List
import sys
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int])->int:
        leng = len(nums)
        windowlen = sys.maxsize
        i = 0
        sum = 0
        for j in range(0, leng):
            sum += nums[j]
            while sum >= s:
                windowlen = min(windowlen, j - i + 1)
                sum -= nums[i]
                i += 1

        if windowlen == sys.maxsize:
            return 0
        else:
            return windowlen

Swift Code

class Solution {
    func minSubArrayLen(_ target: Int, _ nums: [Int]) -> Int {

        var sum = 0, windowlen = Int.max, i = 0
        for j in 0..<nums.count {
            sum += nums[j]
            while sum >= target {
                windowlen = min(windowlen, j - i + 1)
                sum -= nums[i]
                i += 1
            }
        }
        return windowlen == Int.max ? 0 : windowlen
    }
}

Go Code:

func minSubArrayLen(target int, nums []int) int {
    length := len(nums)
    winLen := length + 1
    i := 0
    sum := 0
    for j := 0; j < length; j++ {
        sum += nums[j]
        for sum >= target {
            winLen = min(winLen, j - i + 1)
            sum -= nums[i]
            i++
        }
    }
    if winLen == length + 1 {
        return 0
    }
    return winLen
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}