LeetCode 0209.长度最小的子数组

长度最小的子数组

题目描述

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

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

示例 1：

1
2
3


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

示例 2：

1
2


输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

1
2


输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

思路

题目要求

给定一个数组和一个正整数，找到最小子数组的和≥给定的正整数
返回最小子数组的长度，若不存在则返回0

暴力解法是写两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是O(n^2)

滑动窗口法：不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。定义一个左指针和一个右指针，右指针向前移动，直到找到子串和大于给定数停止移动，并记录子串长度。此时，左指针向前移动，找子串的最小长度并记录。当子串和小于给定数时，左指针停止移动，右指针开始向前移动，直到找到子串和大于给定数停止移动……这样可以将数组中所有可能性都计算一遍。时间复杂度是O(n)。

滑动窗口法也可以理解为双指针法的一种，只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。

注意

左右指针的起始位置都置为-1，与后面先移动指针后累加的顺序保持一致
为了与后面比较各子串长度，所以将最小子串初值置为数组长度+1，最后返回最小子串长度进行判断
循环条件为左指针不超过右指针，当右指针移动后越界也结束循环

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


func minSubArrayLen(target int, nums []int) int {
    length := len(nums)
    leftIndex, rightIndex := -1, -1
    minSubLen := length + 1
    sum := 0
    for leftIndex <= rightIndex {
        if sum < target {
            rightIndex++
            if rightIndex > length-1 {
                break
            }
            sum += nums[rightIndex]
        } else {
            leftIndex++
            if rightIndex-leftIndex+1 < minSubLen {
                minSubLen = rightIndex - leftIndex + 1
            }
            sum -= nums[leftIndex]
        }
    }
    if minSubLen == length+1 {
        return 0
    } else {
        return minSubLen
    }
}

Link

GitHub