图解：长度最小的子数组（LeetCode209）

种一棵树最好的时间是十年前，其次是现在 ——Dambisa Moyo

今天开始记录分享自己的算法学习之路，先定一个小目标，我先写它个100天！

虽然我目前的水平和写作都亟待提升，但是一天进步一点点我们就进步巨大！

希望我们一起坚持，一起学习，一起更优秀！

每日一笑

手指骨折去挂骨科。医生：“手指怎么断的?”

我说：“我有强迫症。”

医生：“你手指断了跟强迫症有什么关系?”

我说：“十个手指九个都响，就它不响。”

题目描述

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

示例:

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

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

解题思路

首先，由题中的「连续」自然的想到「双指针」解法。

定义 start，end 两个指针，一个指向左边起始位置；一个指向右边结束位置，根据题目场景此题将左右指针初始化为数组下标0处。然后求和 sum 进行判断，如果 sum < s ，则 左指针 start 右移，如果 sum ≥ s 即符合要求，则记录长度 end - start + 1，并且 end 右移继续判断。

文字理解可能比较抽象，能用图表示的就少BB，上图

代码实现

想归想，但一定要写代码实现！因为做出来和想出来是两码事。我写的第一版代码有个地方没处理好结果写成了暴力法

一顿操作猛如虎，击败用户一十五

第一版的代码如下：第二层的 for 循环没处理好，所以时间复杂度很高为 O(n^2)

因为本人现在工作转成 Go 语言，所以主要以 Go 为主，但是算法最重要的是了解思想！用什么语言不过是表达形式不同罢了

// 暴力 // Go func minSubArrayLen(s int, nums []int) int { length := len(nums) ans := length + 1 for start := 0; start < length; start++ { sum := nums[start] if sum >= s { return 1 } else { for end := start + 1; end < length; { sum += nums[end] if sum >= s { len := end - start + 1 ans = myutil.MinInt(ans, len) // 注：这里的 MinInt() 由于经常用到，故我将其放在工具包中。LeetCode运行时记得写在本文件中 break } else { end++ } } } } if ans > length { return 0 } return ans } // LeetCode 运行时可以写在 func MinInt(x, y int) int { if x < y { return x } return y }

优化后的代码如下：时间复杂度降为了O(n)，即外层的 for end < length

// 双指针 // Go func minSubArrayLen(s int, nums []int) int { length := len(nums) // 内置函数得出数组长度 if length == 0 { return 0 } ans := math.MaxInt32 // 定义结果为最大值 start, end := 0, 0 // 左右边界 sum := 0 // 临时变量存和 // 遍历数组 for end < length { // 求和 sum += nums[end] // 当 sum 大或等于目标 s 时，则更新子数组的最小长度（此时子数组的长度是 end-start+1），并减去 nums[start] ，将 start 右移 for sum >= s { ans = myutil.MinInt(ans, end-start+1) // 注：这里的 MinInt() 由于经常用到，故我将其放在工具包中。LeetCode运行时记得写在本文件中 sum -= nums[start] start++ } // sum 小于 s，将 end 右移 end++ } // 若果 ans 未改动，无符号条件返回 0 if ans == math.MaxInt32 { return 0 } return ans } // LeetCode 运行时可以写在 func MinInt(x, y int) int { if x < y { return x } return y }

运行效率就好多了

再给一个熟悉的 Java 版本

// Java class Solution { public int minSubArrayLen(int s, int[] nums) { int n = nums.length; if (n == 0) { return 0; } int ans = Integer.MAX_VALUE; int start = 0, end = 0; int sum = 0; while (end < n) { sum += nums[end]; while (sum >= s) { ans = Math.min(ans, end - start + 1); sum -= nums[start]; start++; } end++; } return ans == Integer.MAX_VALUE ? 0 : ans; } }

郑重声明：

所展示代码已通过 LeetCode 运行通过，请放心食用～

在唠唠嗑

很多人都想养成好习惯，但大多数人却是三分钟热度。为了我们能一起坚持下去，决定制定如下计划（福利）

一起学算法，打卡领红包！

参与方式：关注我的原创微信公众号「Kevin的学堂」，一起学习，一起更优秀！

打卡规则为：

「留言」“打卡XXX天” ➕「分享」到朋友圈

奖励：

连续打卡 21 天，联系本人获取 6.6 元红包一个！

连续打卡 52 天，联系本人获取 16.6 元红包一个！

连续打卡 100 天，联系本人获取 66.6 元红包一个！

都看到这儿了，给俺点个赞呗，可以让更多的人看到这篇文章，顺便激励下我，嘻嘻。