LeetCode209.滑动窗口算法原理图解(Kotlin语言):长度最小的子数组
题目:
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 sum ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。 进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
滑动窗口的算法原理图解
最小长度的子数组.gif
Sliding Window 算法思想源代码欣赏:
代码语言：javascript复制class Solution {
fun minSubArrayLen(s: Int, nums: IntArray): Int {
var ans = Int.MAX_VALUE
val n = nums.size
var left = 0 // 左指针
var right = 0 // 右指针
var sum = 0 // 窗口中元素的和
while (right < n) {
// 窗口中的元素小于目标值，右指针向右移，扩大窗口
sum = nums[right]
right = 1
// 窗口中的元素大于目标值，左指针向右移，缩小窗口
while (sum >= s) {
// 窗口中的元素大于目标值,此时的窗口长度为 ans
ans = Math.min(ans, right - left)
// 在左指针向右移1位之前, 先把 left 位置此时的值,从 sum 中减去
sum -= nums[left]
left = 1
}
}
return if (ans != Int.MAX_VALUE) ans else 0
}
}算法复杂度:
时间复杂度: O(n) 空间复杂度: O(1)
相关源代码和空间时间复杂度分析:
代码语言：javascript复制package i
import kotlin.math.min
/**
* @author: Jack
* 2020-04-20 01:08
*/
/**
* 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 sum ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/**
* 常规思路:暴力破解
*
* 时间复杂度：O(n^3)
对数组里的每一个元素，我们从它开始枚举所有的子数组，需要的时间为 O(n^2)
将每一个子数组求和的时间复杂度为：O(n)。
所以总时间复杂度为：O(n^2 * n) = O(n^3)
空间复杂度：O(1)。只是用了常数个额外变量。
作者：LeetCode
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
fun minSubArrayLen1(s: Int, nums: IntArray): Int {
var ans = Int.MAX_VALUE
val n = nums.size
for (i in 0 until n) {
// break to here, i
for (j in i until n) {
var sum = 0
// 计算当前子数组的元素和
for (k in i..j) {
sum = nums[k]
}
if (sum >= s) {
ans = min(ans, j - i 1)
break // Found the smallest subarray with sum>=s starting with index i, hence move to next index
}
}
}
return if (ans != Int.MAX_VALUE) ans else 0
}
/**
* 滑动窗口:
* 解题思路
思路：
当输出或比较的结果在原数据结构中是连续排列的时候，可以使用滑动窗口算法求解。
将两个指针比作一个窗口，通过移动指针的位置改变窗口的大小，观察窗口中的元素是否符合题意。
初始窗口中只有数组开头一个元素。
当窗口中的元素小于目标值，右指针向右移，扩大窗口。
当窗口中的元素大于目标值，比较当前窗口大小是否为最小值，左指针向右移，缩小窗口。
算法复杂度:
时间复杂度：O(n) 。每个指针移动都需要 O(n) 的时间。
每个元素至多被访问两次，一次被右端点访问，一次被左端点访问。
空间复杂度： O(1) , left，right, sum， ans 以及 i这些变量只需要常数个空间。
作者：lxiaocode
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/java-209-chang-du-zui-xiao-de-zi-shu-zu-hua-dong-c/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
fun minSubArrayLen2(s: Int, nums: IntArray): Int {
var ans = Int.MAX_VALUE
val n = nums.size
var left = 0 // 左指针
var right = 0 // 右指针
var sum = 0 // 窗口中元素的和
while (right < n) {
// 窗口中的元素小于目标值，右指针向右移，扩大窗口
sum = nums[right]
right = 1
// 窗口中的元素大于目标值，左指针向右移，缩小窗口
while (sum >= s) {
// 窗口中的元素大于目标值,此时的窗口长度为 ans
ans = min(ans, right - left)
// 在左指针向右移1位之前, 先把 left 位置此时的值,从 sum 中减去
sum -= nums[left]
left = 1
}
}
return if (ans != Int.MAX_VALUE) ans else 0
}
fun main() {
val s = 7
val nums = intArrayOf(2, 3, 1, 2, 4, 3)
val s1 = minSubArrayLen1(s, nums)
val s2 = minSubArrayLen2(s, nums)
println("s1=$s1")
println("s2=$s2")
}Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s.
If there isn't one, return 0 instead.
Example:
代码语言：javascript复制Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray `[4,3]` has the minimal length under the problem constraint.Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(nlog n).
参考资料:
力扣（LeetCode） ：https://leetcode-cn.com/problems/minimum-size-subarray-sum
