专栏首页一个会写诗的程序员的博客LeetCode209.滑动窗口算法原理图解(Kotlin语言):长度最小的子数组

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

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 算法思想源代码欣赏:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Eric S. Raymond:如何成为一名黑客如何成为一名黑客How To Become A Hacker

    http://www.0x08.org/docs/hacker-howto.html#hacker-howto

    一个会写诗的程序员
  • Java 反射工具类 ReflectionUtil

    一个会写诗的程序员
  • 教育行业BP怎么写?参考这个案例可避开80%的坑丨案例

    导读:为了帮助广大创业者有针对性地提高BP撰写技能、提升融资成功率,疯狂BP将不定时挑选一些商业计划书(包含融资未成功与融资成功的),通过对BP中每一页的解读,...

    一个会写诗的程序员
  • 借Reaper僵尸网络推广免费IP扫描器 然后在IP扫描器里面放个后门

    用户1697231
  • 安恒信息受邀出席全球未来网络发展峰会 “宁聚” 网络强国新力量

    以“创新 引领 未来”为主题的2018第二届全球未来网络发展峰会5月11日-12日在南京江宁未来网络小镇隆重举行。400多名国内外未来网络领域的专家、学者及知名...

    安恒信息
  • 爬了下知乎神回复,已笑趴~~~

    A: 这暗示了,在你连iPhone都买不起的时候,他就买了房子。 世界真是不公平呀!

    良月柒
  • Mybatis高级查询(一):resultMap与resultType

    resultType:将查询结果按照sql列名pojo属性名一致性映射到pojo中

    用户7649162
  • 提高GIT中代码质量的七点优秀实践

    毋庸置疑,由于Git允许开发人员能够同时在相同的代码库上工作,因此它在各类软件开发中起到了重要的作用。不过,我们也发现部分开发人员由于未能遵循Git的相关最佳实...

    Java帮帮
  • 2016年移动安全趋势及威胁预测

    2015年已经过去,这一年间发生了很多令我们很震惊的事件,透过这些大事件和漏洞,我们可以预测一下2016年移动安全趋势和可能存在的安全威胁。 1. 恐怖威胁 ...

    FB客服
  • Git的艺术—分支管理

    Git的开发者—— Linus Benedict Torvalds,22岁就创建了Linux系统,发展到2005年的时候,用了仅两周的时间写了一个分布式版本控制...

    腾讯工蜂

扫码关注云+社区

领取腾讯云代金券