「力扣」第 209 题:长度最小的子数组(中等)


「力扣」第 209 题:长度最小的子数组(中等)

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

示例:

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

进阶:

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

方法一:暴力解法(超时)

  • 暴力解法需要使用三层循环。

Java 代码:

public class Solution {

    public int minSubArrayLen(int s, int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }

        int minLen = len + 1;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                int sum = 0;
                for (int k = i; k <= j; k++) {
                    sum += nums[k];
                }

                if (sum >= s) {
                    minLen = Math.min(minLen, j - i + 1);
                }
            }
        }

        if (minLen == len  + 1){
            return 0;
        }
        return minLen;
    }
}

复杂度分析

  • 时间复杂度:$O(N^3)$,这里 $N$ 是数组的长度。
  • 空间复杂度:$O(1)$。

方法二:构建前缀和数组(思路:空间换时间)

Java 代码:

public class Solution {

    public int minSubArrayLen(int s, int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        // 由于 nums 全都是正整数,因此 preSum 严格单调增加
        // preSum 表示 sum(nums[0..i))
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        int minLen = len + 1;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (preSum[j + 1] - preSum[i] >= s) {
                    minLen = Math.min(minLen, j - i + 1);
                }
            }
        }
        if (minLen == len + 1) {
            return 0;
        }
        return minLen;
    }

    public static void main(String[] args) {
        int s = 7;
        int[] nums = {2, 3, 1, 2, 4, 3};
        Solution2 solution2 = new Solution2();
        int minSubArrayLen = solution2.minSubArrayLen(s, nums);
        System.out.println(minSubArrayLen);
    }
}

复杂度分析

  • 时间复杂度:$O(N^2)$,这里 $N$ 是数组的长度。
  • 空间复杂度:$O(1)$。

方法三:前缀和数组 + 二分法(思路:空间换时间)

充分利用题目给出的条件:正整数。

  • 利用「数组是正整数」这个条件,构造前缀和数组,前缀和数组一定是严格增加的;
  • 任意区间和可以通过前缀和数组得到,这是我们常见的一种做法。 起点固定的时候,区间越长,区间和越大。

Java 代码:构造前缀和数组,使用二分查找法,要考虑一些边界条件,编码易出错,了解即可

public class Solution {

    // 构造前缀和数组,使用二分查找算法

    public int minSubArrayLen(int s, int[] nums) {

        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        // 由于 nums 全都是正整数,因此 preSum 严格单调增加
        // preSum 表示 sum(nums[0..i))
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        // System.out.println(Arrays.toString(preSum));
        int minLen = len + 1;
        // 遍历一次,找到和大于等于 s 的最大下标
        for (int i = 0; i < len; i++) {
            // 对于前缀和数组来说,有 1 个位置的偏移,找使得区间和 sum[left..right] >= s 的最大的 left
            int left = 0;
            int right = i;
            while (left < right) {
                int mid = left + (right - left + 1) / 2;
                // 什么时候解我们不需要呢,sum(nums[mid..i]) < s
                if (preSum[i + 1] - preSum[mid] < s) {
                    // 下一轮搜索区间在 [left, mid - 1]
                    right = mid - 1;
                } else {
                    left = mid;
                }
            }

            // 这里后处理
            // System.out.println("left = " + left);
            // System.out.println("区间和 = " + (preSum[i + 1] - preSum[left]));
            if (preSum[i + 1] - preSum[left] >= s) {
                minLen = Math.min(minLen, i - left + 1);
            }
        }

        if (minLen == len + 1) {
            return 0;
        }
        return minLen;
    }


    public static void main(String[] args) {
        int s = 15;
        int[] nums = {1, 2, 3, 4, 5};
        Solution3 solution3 = new Solution3();
        int minSubArrayLen = solution3.minSubArrayLen(s, nums);
        System.out.println(minSubArrayLen);
    }
}

说明:虽然这个思路的解法时间复杂度和空间复杂度都不如「滑动窗口」,但我们也建议大家掌握。这是因为:

  • 计算区间和,转向计算「前缀和」是常见的思路;
  • 并且,根据输入「给定一个含有 n 个正整数」,前缀和一定单调增加,利用单调性确定一个下标,使用二分查找的思路也非常自然。
  • 「二分查找」是很常见的算法思想,「前缀和」是很常见的算法技巧。我们都建议大家掌握。

复杂度分析

  • 时间复杂度:$O(N \log N)$,这里 $N$ 是数组的长度。
  • 空间复杂度:$O(N)$。

方法四:滑动窗口

在做完了第 3 题、第 76 题以后,这道题就变得非常简单了,因为维护滑动窗口内的性质变得简单了。

  • 情况 1 :当区间和小于 s 的时候,右区间的端点向右扩展,这一点依赖外层循环的遍历就可以完成;

  • 情况 2 :一旦区间和大于等于 s,尝试一步一步缩小左区间端点,看看是否能得到一个更短的区间,满足区间和 >=s,这一步通过一个内层循环实现。

Java 代码:

public class Solution {

    // 向右边扩散得到和越来越大
    // 向左边界扩散得到和越来越小

    public int minSubArrayLen(int s, int[] nums) {
        int len = nums.length;

        int left = 0;
        int right = 0;

        int sum = 0;
        // 保持性质:[left, right) >= s
        int minLen = len + 1;
        while (right < len) {
            sum += nums[right];
            right++;

            while (sum >= s) {
                minLen = Math.min(minLen, right - left);

                sum -= nums[left];
                left++;
            }
        }

        if (minLen == len + 1) {
            return 0;
        }
        return minLen;
    }
}

Python 代码:在理解的基础上,记住下面这个写法,右指针也是用于遍历的指针

from typing import List


class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        size = len(nums)
        # 特判
        if size == 0:
            return 0

        left = 0
        right = 0
        # 区间和
        interval_sum = 0
        min_len = size + 1
        while right < size:
            interval_sum += nums[right]
            right += 1

            while interval_sum >= s:
                min_len = min(min_len, right - left)
                interval_sum -= nums[left]
                left += 1
        if min_len == size + 1:
            return 0
        return min_len


if __name__ == '__main__':
    s = 7
    nums = [2, 3, 1, 2, 4, 3]
    solution = Solution()
    result = solution.minSubArrayLen(s, nums)
    print(result)

复杂度分析

  • 时间复杂度:$O(N)$,这里 $N$ 是数组的长度。
  • 空间复杂度:$O(1)$。

(本节完)


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 220 题:存在重复元素 III 「力扣」第 220 题:存在重复元素 III
「力扣」第 220 题:存在重复元素 III传送门:220. 存在重复元素 III; 题解地址:滑动窗口 + 二叉搜索树找上下边界(Python 代码、Java 代码)。 给定一个整数数组,判断数组中是否有两个不同的索引 i 和 j,使得
下一篇 
「力扣」第 76 题:最小覆盖子串 「力扣」第 76 题:最小覆盖子串
「力扣」第 76 题:最小覆盖子串 中文网址:76. 最小覆盖子串 ; 英文网址:76. Minimum Window Substring 。 给定一个字符串 S 和一个字符串 T,请在 S 中找出包含 T 所有字母的最小子串。 示
  目录