LeetCode209.滑动窗口算法原理图解(Kotlin语言):长度最小的子数组

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
    }
}

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")

}

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.