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

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

示例:

输入: s = 7, nums = [2,3,1,2,4,3]

输出: 2

解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

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

解题思路

当输出或比较的结果在原数据结构中是连续排列的时候,可以使用滑动窗口算法求解。 将两个指针比作一个窗口,通过移动指针的位置改变窗口的大小,观察窗口中的元素是否符合题意。

  • 初始窗口中只有数组开头一个元素。

  • 当窗口中的元素小于目标值,右指针向右移,扩大窗口。

  • 当窗口中的元素大于目标值,比较当前窗口大小是否为最小值,左指针向右移,缩小窗口。

算法复杂度:

时间复杂度:O(n) 。每个指针移动都需要 O(n) 的时间。

每个元素至多被访问两次,一次被右端点访问,一次被左端点访问。

空间复杂度:O(1) ,  left,right,  sum, ans 以及 i这些变量只需要常数个空间。

滑动窗口的算法原理图解

最小长度的子数组

Sliding Window 算法思想源代码欣赏:

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)

相关源代码和空间时间复杂度分析:

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:

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

算法相关文章:

[数据结构与算法&nbsp;(Kotlin&nbsp;语言)]&nbsp;1.冒泡排序(Bubble&nbsp;Sort)

快速排序&nbsp;Java&nbsp;实现

LRU&nbsp;&nbsp;Cache&nbsp;的几种&nbsp;Java&nbsp;实现

你真的懂协程吗&nbsp;?&nbsp;&nbsp;Kotlin&nbsp;协程&nbsp;Coroutine&nbsp;全解析

一道有难度的经典大厂面试题:如何快速判断某&nbsp;URL&nbsp;是否在&nbsp;20&nbsp;亿的网址&nbsp;URL&nbsp;集合中?

Linux&nbsp;内核的&nbsp;4&nbsp;大&nbsp;IO&nbsp;调度算法

实时协同编辑的实现:&nbsp;编辑锁,&nbsp;OT算法

【BAT&nbsp;面试题宝库附详尽答案解析】图解分布式一致性协议&nbsp;Paxos&nbsp;算法

Kotlin 开发者社区

国内第一Kotlin 开发者社区公众号,主要分享、交流 Kotlin 编程语言、Spring Boot、Android、React.js/Node.js、函数式编程、编程思想等相关主题。

越是喧嚣的世界,越需要宁静的思考。

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章