全栈开发知识库

30.长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1:

  • 输入：target = 7, nums = [2,3,1,2,4,3]
  • 输出：2
  • 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2:

  • 输入：target = 4, nums = [1,4,4]
  • 输出：1

示例 3:

  • 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
  • 输出：0

提示:

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

进阶:

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

思路

暴力循环(O(n²))

枚举每个启动l，向右累加直到 >= target，记录最短长度，这能过，但不是最优。

问题在于每次换起点都要从头累加，做了大量重复计算。

滑动窗口(O(n))

什么是滑动窗口?

滑动窗口是一种处理连续区间问题的算法技巧。

它维护一个由两个指针(left和right)框定的窗口，这个窗口在数据上从左向右滑动，通过动态调整窗口的两个边界，避免重复计算，把很多O(n²)的暴力问题优化到O(n)。

为什么能用滑动窗口?

关键在于题目条件: 全是正整数，这意味着:

  • 窗口右边界right右移(会加入新元素)，窗口的和只会增加不会减小。

  • 窗口左边界left右移(会移除元素)，窗口的和只会减小不会增加。

  • 两条边都只能往右走，从不回头，正是因为两个指针不回头，每个元素最多被right碰一次、被left碰一次，总共2n次操作，所以复杂度为O(n)

滑动窗口能成立的要求: 单调性

这是最本质的原理，滑动窗口能用的前提是窗口的某个属性随边界移动而单调变化。

这种单调性是滑动窗口成立的前提。

如果数组含有负数，加入元素不一定变大，移除也不一定变小，滑动窗口就失效了。

核心思想:

维护一个[left, right]的窗口，用一个变量sum记录窗口内元素之和:

  • 扩张窗口: right不断右移，把nums[right]加入sum

  • 收缩窗口: 一旦sum >= target，说明当前窗口满足条件，此时尝试缩小窗口 -- 记录当前长度，然后把nums[left]移出、left ++，看能不能在仍满足 >= target 的前提下变得更短

  • 用while而非if来收缩，因为可能连续移出多个元素仍然能满足条件。 

class Solution {
    fun minSubArrayLen(target: Int, nums: IntArray): Int {
        // 注意这里必须是MAX_VALUE，因为如果你是0，在那下面min的时候就始终一直是0
        var result = Int.MAX_VALUE

        var leftIndex = 0
        var windowSum = 0
        for (rightIndex in nums.indices) {
            windowSum += nums[rightIndex]

            while (windowSum >= target) {
                result = min(result, rightIndex - leftIndex + 1)
                windowSum -= nums[leftIndex]
                leftIndex ++
            }
        }

        return if (result == Int.MAX_VALUE) { 0 } else { result }
    }
}

复杂度分析:

  • 时间复杂度：O(n)，其中 n 是数组的长度。指针 start 和 end 最多各移动 n 次。

  • 空间复杂度：O(1)。

进阶要求解法: 前缀和 + 二分查找 (O(nlog n))

  • 构造前缀和数组 prefix，其中 prefix[i] = nums[0] + ... + nums[i-1]（prefix[0] = 0）

  • 子数组 [l, r] 的和 = prefix[r+1] - prefix[l]

  • 对每个左端点 i，我们要找最小的 j，使得 prefix[j] - prefix[i] >= target，即 prefix[j] >= prefix[i] + target

  • 因为全是正整数，prefix 严格递增（有序），所以可以用二分查找快速定位最小的 j。

class Solution {
    fun minSubArrayLen(target: Int, nums: IntArray): Int {
        val n = nums.size
        // prefix[i] 表示前 i 个元素之和；prefix[0] = 0
        // 这里为什么size要是n+1?
        // 考虑从下标 0 开始的子数组 [0, r]，它的和 = prefix[r+1] - prefix[0]。
        // 这里必须用到 prefix[0]。如果 prefix[0] 不存在，你就没法表示「从第一个元素开始」的子数组的和。
        val prefix = IntArray(n + 1)
        for (i in 1..n) {
            prefix[i] = prefix[i - 1] + nums[i - 1]
        }

        var minLen = Int.MAX_VALUE
        for (i in 0..n) {
            // 要找最小的 j，使 prefix[j] >= prefix[i] + target
            val needed = prefix[i] + target
            val bound = lowerBound(prefix, needed)
            if (bound != -1) {
                minLen = minOf(minLen, bound - i)
            }
        }

        return if (minLen == Int.MAX_VALUE) 0 else minLen
    }

    // 在升序数组中找第一个 >= key 的下标，找不到返回 -1
    private fun lowerBound(arr: IntArray, key: Int): Int {
        var lo = 0
        var hi = arr.size            // 左闭右开 [lo, hi)
        var result = -1
        while (lo < hi) {
            val mid = lo + (hi - lo) / 2
            if (arr[mid] >= key) {
                result = mid          // 记录候选，继续往左找更小下标
                hi = mid
            } else {
                lo = mid + 1
            }
        }
        return result
    }
}

复杂度分析:

  • 时间复杂度：O(nlog n)。

  • 空间复杂度：O(n) 前缀和数组。

  • 邮箱 ：charon.chui@gmail.com
  • Good Luck!