滑动窗口解leetcode之209-长度最小的数组

leetcode上的题目描述:

给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其和>=target的长度最小的连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回0.

示例:

1
2
3


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

通过这题学习了滑动窗口算法，前面还难理解，找了些相关资料，理解吸引了下，特记录下，防止下次遗忘能重新拾起来。

滑动窗口，其实解释起来很简单:

1. 先定义两个指针,左/右指针。初始值都为0
2. 最开始移动右指针，一直移动到满足某个条件
3. 当条件满足时，停止移动右指针，转而开始移动左指针。尝试找到最优解
4. 当移动左指针不满足条件时，继续移动右指针，直到满足。
5. 重复2-4步，直到右指针移动到数组的最后一个元素

感谢负雪明烛的分享

算法重点:

以右指针作为驱动，拖着左指针向前走。
右指针每次只移动一步，而左指针在内部while循环中每次可能移动多步
右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间

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
27
28
29
30


func minSubArrayLen(target int, nums []int) int {
    // 滑动窗口算法
    // left,right指针， result存储临时最优解, total存储当前窗口内的最大值
    var left, right, result, total int
    // 假设最长为数组长度+1，即真实情况不可能有这么长，特殊标记下
    result = len(nums) + 1
    for right = 0; right < len(nums); right++ {
        total += nums[right]
        // 当条件满足时，移动左指针，一直移动到满足条件
        for total >= target {
            // 记录临时最优解,后续还有可能有最优解，临时存储起来，后续再判断
            curr := right - left
            if curr < result {
                result = curr
            }
             // 移动左指针时，total的值则要减去最左边的值，窗口已经不包含它了
            total -= nums[left]
            left += 1  
        }
        // 条件不满足时，移动右指针，即进入下个循环，right++
        continue
    }

    // 最后对结果做一个判断
    if result == len(nums) + 1 {
         return 0
    }
    // 因为索引是从0开始，最后加1
    return result + 1
}

文章目录