前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode209.滑动窗口算法原理图解(Kotlin语言):长度最小的子数组

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

作者头像
一个会写诗的程序员
修改2023-09-21 17:00:21
1.3K0
修改2023-09-21 17:00:21
举报
文章被收录于专栏:一个会写诗的程序员的博客

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

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • LeetCode209.滑动窗口算法原理图解(Kotlin语言):长度最小的子数组
  • 题目:
  • 示例:
  • 滑动窗口的算法原理图解
  • 相关源代码和空间时间复杂度分析:
  • 参考资料:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档