[Leetcode][209. 长度最小的子数组] 5种方法：暴力，双指针，前缀和，前缀和 + 二分查找，二分查找

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 5.4k 阅读时长 ≈ 5 分钟

By Long Luo

Leetcode 209. 长度最小的子数组 题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
209. 长度最小的子数组

给定一个含有$n$个正整数的数组和一个正整数$\textit{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 <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
 
进阶：
如果你已经实现 $O(n)$ 时间复杂度的解法, 请尝试设计一个 $O(n\log n)$ 时间复杂度的解法。

方法一：暴力法

思路与算法：

很容易想到，使用 \(2\) 个循环，枚举 \(\textit{nums}\) 中的每个下标作为子数组的开始下标，对于每个子数组 \(i\)，满足 \(i \le x \le j\)，使得：

\[ sum=\sum_{x=i}^{j}\textit{nums}[x] \ge $\textit{target} \]

，并更新子数组的最小长度 \(j-i+1\)。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int minSubArrayLen_bf(int target, int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int len = nums.length;
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < len; i++) {
        int sum = 0;
        for (int j = i; j < len; j++) {
            sum += nums[j];
            if (sum >= target) {
                ans = Math.min(ans, j - i + 1);
                break;
            }
        }
    }

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

复杂度分析：

  • 时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
  • 空间复杂度：\(O(1)\)。

方法二：双指针 + 滑动窗口

思路与算法：

因为求连续子数组的和大于某个值，那么很容易想到使用滑动窗口，使用双指针 \(left\) 和 \(right\) 表示一个窗口：

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

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minSubArrayLen_sw(int target, int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int len = nums.length;
    int ans = Integer.MAX_VALUE;
    int sum = 0;
    int left = 0;
    int right = 0;
    while (right < len) {
        sum += nums[right];
        while (sum >= target) {
            ans = Math.min(ans, right - left + 1);
            sum -= nums[left];
            left++;
        }

        right++;
    }

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

复杂度分析：

  • 时间复杂度：\(O(N)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度，指针 \(\textit{start}\) 和 \(\textit{end}\) 最多各移动 \(n\) 次。
  • 空间复杂度：\(O(1)\)。

方法三：前缀和 + 滑动窗口

思路与算法：

对于求连续数组之和的问题，还可以使用前缀和来求解。

我们创建一个数组 \(\textit{prefixSums}\) 用于存储数组 \(\textit{nums}\) 的前缀和，其中 \(\textit{prefixSums}[i]\) 表示从 \(\textit{nums}[0]\) 到 \(\textit{nums}[i-1]\) 的元素和。

得到前缀和之后，我们可以使用滑动窗口来计算最小的窗口长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int minSubArrayLen(int target, int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int len = nums.length;
    int ans = Integer.MAX_VALUE;
    int[] prefixSums = new int[len + 1];
    for (int i = 1; i <= len; i++) {
        prefixSums[i] = prefixSums[i - 1] + nums[i - 1];
    }

    int left = 0;
    int right = 1;
    while (right <= len) {
        int sum = prefixSums[right] - prefixSums[left];
        if (sum >= target) {
            ans = Math.min(ans, right - left);
            left++;
        } else {
            right++;
        }
    }

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

复杂度分析：

  • 时间复杂度：\(O(N^2)\) ，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
  • 空间复杂度：\(O(N)\) 。

方法四：前缀和 + 二分查找

思路与算法：

在方法三的基础上，找到长度最小的子数组需要 \(O(n)\) 的时间，因为数组中元素都 \(>0\)，所以前缀和中元素值都是递增的，那么可以使用二分查找，将时间优化到 \(O(logn)\)。

得到前缀和之后，对于每个开始下标 \(i\)，可通过二分查找得到 \(\ge i\) 的最小下标 \(\textit{bound}\)，使得 \(\textit{prefixSums}[\textit{bound}]-\textit{prefixSums}[i-1] \ge \text{target}\)，并更新子数组的最小长度 \(\textit{bound} - (i-1)\)。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public int minSubArrayLen_prefix_bs(int target, int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int len = nums.length;
    int ans = Integer.MAX_VALUE;
    int[] prefixSums = new int[len + 1];
    for (int i = 1; i <= len; i++) {
        prefixSums[i] = prefixSums[i - 1] + nums[i - 1];
    }

    for (int i = 1; i <= len; i++) {
        int upperBound = binarySearch(prefixSums, i, len, target + prefixSums[i - 1]);
        if (upperBound != -1) {
            ans = Math.min(ans, upperBound - i + 1);
        }
    }

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

public int binarySearch(int[] nums, int left, int right, int target) {
    if (nums[right] < target) {
        return -1;
    }

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }

    return nums[left] >= target ? left : -1;
}

复杂度分析：

  • 时间复杂度：\(O(N \log N)\)，其中 \(N\) 是数组的长度。需要遍历每个下标作为子数组的开始下标，遍历的时间复杂度是 \(O(N)\)，对于每个开始下标，需要通过二分查找得到长度最小的子数组，二分查找得时间复杂度是 \(O(\log N)\)，因此总时间复杂度是 \(O(N \log N)\)。
  • 空间复杂度：\(O(N)\)，需要额外创建数组 \(\textit{prefixSums}\) 存储前缀和。

方法五：二分查找

思路与算法：

方法四中二分查找的关键在于 \(\textit{prefixSums}\) 数组的定义，这里提供另外一种二分查找的思路。

因为数组中元素都 \(>0\)，而寻找连续的数字和大于等于 \(\textit{target}\) 的最小长度，要寻找的 \(\textit{minLen}\) 的范围在 \(0\) 到 \(len\) 之间。

但如何进行二分呢？

长度为 \(1\) 的所有连续数字中最大的和、长度为 \(2\) 的所有连续数字中最大的和、长度为 \(3\) 的所有连续数字中最大的和、…、长度为 \(len\) 的所有连续数字中最大的和，同样是一个升序数组。

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

对于长度为 \(len\) 的数组，我们先去判断长度为 \(len/2\) 的连续数字中最大的和是否大于等于 \(target\)。

  1. 如果 \(\ge target\)，那么需要减少长度，继续判断所有长度为 \(len/4\) 的连续数字；
  2. 如果 \(< target\)，需要增加长度，我们继续判断所有长度为 \((len/2+len)/2\)。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static int minSubArrayLen_bs(int target, int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int len = nums.length;
    int left = 0;
    int right = len;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int maxSum = getMaxSum(nums, mid);
        if (mid == len && maxSum < target) {
            return 0;
        }
        if (maxSum >= target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return left <= len ? left : 0;
}

public static int getMaxSum(int[] nums, int segLen) {
    int sum = 0;
    for (int i = 0; i < segLen; i++) {
        sum += nums[i];
    }

    int ans = sum;
    for (int i = segLen; i < nums.length; i++) {
        sum += nums[i];
        sum -= nums[i - segLen];
        ans = Math.max(ans, sum);
    }

    return ans;
}

复杂度分析：

  • 时间复杂度：\(O(N \log N)\)，其中 \(N\) 是数组的长度。
  • 空间复杂度：\(O(1)\)。

小结

从代码实际运行情况来看，方法三是最快的。

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗