题目描述(中等难度)

找出最小的连续子数组,使得子数组的和大于等于 s

解法一 暴力破解

从第 0 个数字开始,依次添加数字,记录当总和大于等于 s 时的长度。

从第 1 个数字开始,依次添加数字,记录当总和大于等于 s 时的长度。

从第 2 个数字开始,依次添加数字,记录当总和大于等于 s 时的长度。

...

从最后个数字开始,依次添加数字,记录当总和大于等于 s 时的长度。

从上边得到的长度中选择最小的即可。

public int minSubArrayLen(int s, int[] nums) {
    int min = Integer.MAX_VALUE;
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int start = i;
        int sum = 0;
        while (start < n) {
            sum += nums[start];
            start++;
            //当前和大于等于 s 的时候结束
            if (sum >= s) {
                min = Math.min(min, start - i);
                break;
            }
        }
    }
    //min 是否更新,如果没有更新说明数组所有的数字和小于 s, 没有满足条件的解, 返回 0
    return min == Integer.MAX_VALUE ? 0 : min;
}

时间复杂度:O(n²)

解法二 双指针

受到 76 题 Minimum Window Substring 的启示,找一个范围使得其值满足某个条件,然后就会想到滑动窗口,也就是用双指针的方法。和这道题本质是一样的。

用双指针 left 和 right 表示一个窗口。

  1. right 向右移增大窗口,直到窗口内的数字和大于等于了 s。进行第 2 步。
  2. 记录此时的长度,left 向右移动,开始减少长度,每减少一次,就更新最小长度。直到当前窗口内的数字和小于了 s,回到第 1 步。

举个例子,模拟下滑动窗口的过程吧。

s = 7, nums = [2,3,1,2,4,3]

2 3 1 2 4 3
^
l
r
上边的窗口内所有数字的和 2 小于 7, r 右移

2 3 1 2 4 3
^ ^
l r
上边的窗口内所有数字的和 2 + 3 小于 7, r 右移

2 3 1 2 4 3
^   ^
l   r
上边的窗口内所有数字的和 2 + 3 + 1 小于 7, r 右移

2 3 1 2 4 3
^     ^
l     r
上边的窗口内所有数字的和 2 + 3 + 1 + 2 大于等于了 7, 记录此时的长度 min = 4, l 右移

2 3 1 2 4 3
  ^   ^
  l   r
上边的窗口内所有数字的和 3 + 1 + 2  小于 7, r 右移

2 3 1 2 4 3
  ^     ^
  l     r
上边的窗口内所有数字的和 3 + 1 + 2 + 4 大于等于了 7, 更新此时的长度 min = 4, l 右移

2 3 1 2 4 3
    ^   ^
    l   r
上边的窗口内所有数字的和 1 + 2 + 4 大于等于了 7, 更新此时的长度 min = 3, l 右移

2 3 1 2 4 3
      ^ ^
      l r
上边的窗口内所有数字的和 2 + 4 小于 7, r 右移

2 3 1 2 4 3
      ^   ^
      l   r
上边的窗口内所有数字的和 2 + 4 + 3 大于等于了 7, 更新此时的长度 min = 3, l 右移

2 3 1 2 4 3
        ^ ^
        l r
上边的窗口内所有数字的和 4 + 3 大于等于了 7, 更新此时的长度 min = 2, l 右移

2 3 1 2 4 3
          ^
          r
          l
上边的窗口内所有数字的和 3 小于 7, r 右移,结束

代码的话,只需要还原上边的过程即可。

public int minSubArrayLen(int s, int[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    int left = 0;
    int right = 0;
    int sum = 0;
    int min = Integer.MAX_VALUE;
    while (right < n) {
        sum += nums[right];
        right++;
        while (sum >= s) {
            min = Math.min(min, right - left);
            sum -= nums[left];
            left++;
        }
    }
    return min == Integer.MAX_VALUE ? 0 : min;
}

时间复杂度:O(n)

解法三 二分查找

正常想的话,到解法二按理说已经结束了,但题目里让提出一个 O(nlog(n)) 的解法,这里自己也没想出来,分享下 这里O(NLogN)-solutions-both-O(1)-space) 的想法。

看到 log 就会想到二分查找,接着就会想到有序数组,最后,有序数组在哪里呢?

定义一个新的数组,sums[i] ,代表从 0i 的累积和,这样就得到了一个有序数组。

这样做有个好处,那就是通过 sums 数组,如果要求 ij 的所有子数组的和的话,就等于 sums[j] - sums[i - 1]。也就是前 j 个数字的和减去前 i - 1 个数字的和。

然后求解这道题的话,算法和解法一的暴力破解还是一样的,也就是

求出从第 0 个数字开始,总和大于等于 s 时的长度。

求出从第 1 个数字开始,总和大于等于 s 时的长度。

求出从第 2 个数字开始,总和大于等于 s 时的长度。

...

不同之处在于这里求总和时候,可以利用 sums 数组,不再需要累加了。

比如求从第 i 个数字开始,总和大于等于 s 时的长度,我们只需要找从第 i + 1 个数字到第几个数字的和大于等于 s - nums[i] 即可。求 i + 1j 的所有数字的和的话,前边已经说明过了,也就是 sums[j] - sums[i]

public int minSubArrayLen(int s, int[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    int[] sums = new int[n];
    sums[0] = nums[0];
    for (int i = 1; i < n; i++) {
        sums[i] = nums[i] + sums[i - 1];
    }
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        int s2 = s - nums[i]; //除去当前数字
        for (int j = i; j < n; j++) {
            //i + 1 到  j 的所有数字和
            if (sums[j] - sums[i] >= s2) {
                min = Math.min(min, j - i + 1);
            }
        }
    }
    return min == Integer.MAX_VALUE ? 0 : min;
}

至于二分查找,我们只需要修改内层的 for 循环。对于 sums[j] - sums[i] >= s2,通过移项,也就是 sums[j] >= s2 + sums[i] ,含义就是寻找一个 sums[j],使得其刚好大于等于 s2 + sums[i]。因为 sums 是个有序数组,所有找 sum[j] 可以采取二分的方法。

public int minSubArrayLen(int s, int[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    int[] sums = new int[n];
    sums[0] = nums[0];
    for (int i = 1; i < n; i++) {
        sums[i] = nums[i] + sums[i - 1];
    }
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        int s2 = s - nums[i];
        //二分查找,目标值是 s2 + sums[i]
        int k = binarySearch(i, n - 1, sums, s2 + sums[i]);
        if (k != -1) {
            min = Math.min(min, k - i + 1);
        }

    }
    return min == Integer.MAX_VALUE ? 0 : min;
}

//寻求刚好大于 target 的 sums 的下标,也就是大于等于 target 所有 sums 中最小的那个
private int binarySearch(int start, int end, int[] sums, int target) {
    int mid = -1;
    while (start <= end) {
        mid = (start + end) >>> 1;
        if (sums[mid] == target) {
            return mid;
        } else if (sums[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    //是否找到,没有找到返回 -1
    return sums[mid] > target ? mid : -1;
}

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

2020.5.30 更新,感谢 @Yolo 指出,上边的代码虽然 AC 了,但二分查找是有瑕疵的。

sums[mid] > target 我们不能直接更新 end = mid - 1 ,因为此时的 mid 可能是我们要找的解,所以应该改成 end = mid

自己构造了一个反例

59
[10, 50, 5]

这个 caseleetcode 是过不了的。

代码改成下边的样子就可以了。

public int minSubArrayLen(int s, int[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    int[] sums = new int[n];
    sums[0] = nums[0];
    for (int i = 1; i < n; i++) {
        sums[i] = nums[i] + sums[i - 1];
    }
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        int s2 = s - nums[i];
        //二分查找,目标值是 s2 + sums[i]
        int k = binarySearch(i, n - 1, sums, s2 + sums[i]);
        if (k != -1) {
            min = Math.min(min, k - i + 1);
        }

    }
    return min == Integer.MAX_VALUE ? 0 : min;
}

//寻求刚好大于 target 的 sums 的下标,也就是大于等于 target 所有 sums 中最小的那个
private int binarySearch(int start, int end, int[] sums, int target) {
    int mid = -1;
    while (start < end) {
        mid = (start + end) >>> 1;
        if (sums[mid] >= target) {
            end = mid;
        } else {
            start = mid + 1;
        }
    }
    //是否找到,没有找到返回 -1
    return sums[start] >= target ? start : -1;
}

上边还要注意的一点是,我们要找的是大于等于 target最小的下标,所以当 sums[mid] == target 的时候不能立刻停止,需要继续查找。

当然这里其实不用管,因为这里的数组是累和数组,并且都是整数,是严格递增的,当找到相等的时候,前一个一定是小于 target 的。

解法四 二分查找

解法三的二分查找的关键在于 sums 数组的定义,一般情况下也不会往那方面想。还是在 这里O(NLogN)-solutions-both-O(1)-space) 看到的解法,另外一种二分的思路,蛮有意思,分享一下。

题目中,我们要寻找连续的数字和大于等于 s 的最小长度。那么,我们可以对这个长度采取二分的方法去寻找吗?

答案是肯定的,原因就是长度为 1 的所有连续数字中最大的和、长度为 2 的所有连续数字中最大的和、长度为 3 的所有连续数字中最大的和 ... 长度为 n 的所有连续数字中最大的和,同样是一个升序数组。

算法的话就是对长度进行二分,寻求满足条件的最小长度。

对于长度为 n 的数组,我们先去判断长度为 n/2 的连续数字中最大的和是否大于等于 s

  • 如果大于等于 s ,那么我们需要减少长度,继续判断所有长度为 n/4 的连续数字
  • 如果小于 s,我们需要增加长度,我们继续判断所有长度为 (n/2 + n) / 2,也就是 3n/4 的连续数字。

可以再结合下边的代码看一下。

public int minSubArrayLen(int s, int[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    int minLen = 0, maxLen = n;
    int midLen;
    int min = -1;
    while (minLen <= maxLen) {
        //取中间的长度
        midLen = (minLen + maxLen) >>> 1;
        //判断当前长度的最大和是否大于等于 s
        if (getMaxSum(midLen, nums) >= s) {
            maxLen = midLen - 1; //减小长度
            min = midLen; //更新最小值
        } else {
            minLen = midLen + 1; //增大长度
        }
    }
    return min == -1 ? 0 : min;
}

private int getMaxSum(int len, int[] nums) {
    int n = nums.length;
    int sum = 0;
    int maxSum = 0;
    // 达到长度
    for (int i = 0; i < len; i++) {
        sum += nums[i];
    }
    maxSum = sum; // 初始化 maxSum

    for (int i = len; i < n; i++) {
        // 加一个数字减一个数字,保持长度不变
        sum += nums[i];
        sum = sum - nums[i - len];
        // 更新 maxSum
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum;
}

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

这道题的话,通过前边刷题的经验,第一反应就想到了解法二中的双指针。如果不知道双指针的话,应该会想到解法一的暴力破解。

但对于二分查找的解法三和解法四,还是比较难想到的。不过回味完,其实二分查找的关键就是那个递增的有序数列,从而可以每次抛弃一半的可选解。

results matching ""

    No results matching ""