2、题目描述

给定一个含有 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

1、思路分析

这道题要找出该数组中满足其和 ≥ target 的长度最小的连续子数组。

直观的方法是枚举数组中每个下标i作为子数组的开始下标,找到满足条件的下标j,然后更新子数组的最小长度也就是j-i+1,但是这种方法实现可能会超出时间限制。

上面说的方法时间复杂度为O(n2),因为找到长度最小的子数组需要O(n)的时间,要全部找一遍需要O(n2)的时间复杂度,那么能不能将时间优化一下呢。

常见的优化方法,可以使用二分查找,就可以将时间复杂度优化到O(log n),使用二分查找,需要创建一个数组用于存储数组的前缀和,前缀和就是从位置1到位置i这个区间内的所有的数字之和,对于每个开始下标i,通过二分查找得到大于或等于i的最小下标,更新子数组的最小长度。

2、代码实现

代码参考:

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1]; 
        // 为了方便计算,令 size = n + 1 
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
        return ans == Integer.MAX_VALUE ? 0 : ans;

3、时间复杂度

时间复杂度:O(n log n)

其中n是数组的长度,需要遍历每个下标作为子数组的开始下标,通过二分查找得到长度最小的子数组,二分查找的时间复杂度是O(log n),总时间复杂度为O(n log n)。

空间复杂度:O(n)

其中n是数组的长度。

因为这道题保证了数组中的每个元素都是正值。

那么前缀和一定是递增的,可以保证二分查找是不会出现问题的。

如果数组中不是每个元素都为正的话,就不能使用二分来查找位置了。

分类:
后端
标签: