长度最小的子数组

题目

209. 长度最小的子数组

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

找出该数组中满足其总和大于等于 target 的长度最小的

子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：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)) 时间复杂度的解法。

题解

题解一（暴力法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; 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)

image-20241120203654110

题解二（滑动窗口）

看的Leetcode官方题解🤭🤭🤭，可以理解为双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    int start = 0, end = 0;
    int ans = Integer.MAX_VALUE;
    int sum = 0;
    while (end < n ) {
        sum = sum  + nums[end];
        if(sum>=target){
            // 比较那个最小
            ans = Math.min(ans, (end - start)+1);
            // 这里 - nums[end] 是为了防止下次while循环多加了一次
            sum = sum - nums[start] - nums[end];
            ++start;
        }else {
            ++end;
        }
    }
    return ans == Integer.MAX_VALUE ? 0 : ans;
}

image-20241120211709128

题解三（前缀和）

这里首先要理解什么是前缀和，以及前缀和能解决什么问题

1. 快速计算区间和
  • 问题：计算数组中多个区间的和，例如 [l1,r1],[l2,r2],…[l_1, r_1], [l_2, r_2], \dots[l1,r1],[l2,r2],…。
  • 利用前缀和，可以在 O(1)O(1)O(1) 时间内得到每个区间的和。
2. 检测某种和的区间
  • 问题：寻找一个子数组，使其和等于给定的目标值。
  • 思路：利用前缀和，判断是否存在 sums[j] - sums[i] == target，可用哈希表优化查询。
3. 寻找和满足某些条件的区间
  • 问题：寻找子数组使其和大于等于某个值（如“最小长度子数组和问题”）。
  • 思路：结合前缀和与二分搜索，快速找到满足条件的右边界。
4. 处理二维数组的区域和
  • 在二维数组中，前缀和扩展到二维，用于快速计算子矩阵的和。
  • 构建二维前缀和 sums[i][j]sums[i][j]sums[i][j]，表示从左上角到位置 (i,j)(i, j)(i,j) 的元素总和。
5. 解决连续性统计问题
  • 问题：统计数组中满足某些条件的子数组数量（如和为 kkk 的子数组）。
  • 思路：利用前缀和的性质，通过哈希表统计满足条件的前缀和数量。
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
public static int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    int ans = Integer.MAX_VALUE;
    int[] sums = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        // 前缀和
        sums[i] = sums[i - 1] + nums[i - 1];
    }

    for (int i = 1; i <= n; i++) {
        // sums[j] - sums[i] == target 的变形 ==> sums[j] == target + sums[i] 
        int sum = sums[i-1] + target;
        int bound = Arrays.binarySearch(sums, sum);
        if (bound < 0) {
            bound = -bound - 1; // 转换为插入点
        }
        if (bound <= n) {
            ans = Math.min(ans, bound - (i - 1));
        }
    }
    return ans == Integer.MAX_VALUE ? 0 : ans;
}

image-20241120224925009

这位同学简直是天才😂😂😂😂

image-20241120225223045