LeetCode209——长度最小的子数组

LeetCode209——长度最小的子数组

题目描述：

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

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

1.Result01(两层for循环)

暴力解：两层for循环依次寻找，并不断更新子序列长度值。

时间复杂度有点高——O（N2）。

 public static int minSubArrayLen(int target, int[] arr) {
        int min = Integer.MAX_VALUE;//记录当前子序列长度最小值 初始值设为Integer类的常量MAX_VALUE
        for (int i = 0; i < arr.length; i++) {
            int sum = arr[i];//变量sum用于记录子序列中数据之和

            if (sum >= target)//第一个元素就满足，即最小子序列长度为1
                return 1;
            for (int j = i + 1; j < arr.length; j++) {
                sum += arr[j];//在增加子序列长度的同时 累加子序列数据之和

                if (sum >= target) {//满足条件之后 更新当前最短子序列长度的值
                    min = Math.min(min, j - i + 1);
                    break;//跳出内部循环 继续从外部循坏开始往后找
                }
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;//min值仍为初始值，未改变的话 即不存在符合条件的子数组 返回0
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.Result02（滑动窗口）

滑动窗口：不断地调节子序列的起止位置和终止位置，从而得出我们想要的结果。

窗口就是 满足其和 ≥ target 的长度最小的 连续 子数组。

窗口的起始位置如何移动：如果当前窗口的值大于target了，窗口就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

滑动窗口详解链接：代码随想录

 public int minSubArrayLen(int target, int[] arr) {

        int left = 0;//滑动窗口的起始位置

        int sum = 0;//滑动窗口内数值之和

        int result = Integer.MAX_VALUE;//初始值

        for (int right = 0; right < arr.length; right++) {

            sum += arr[right];//存滑动窗口中的数值之和

            while (sum >= target) {//当窗口内元素满足条件的时候 开始缩小窗口
                result = Math.min(result, right - left + 1);//更新窗口最小值
                sum -= arr[left];//减去窗口中删去的元素值
                left++;//缩小窗口起始位置
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20