LeetCode_滑动窗口_前缀和_二分搜索_中等_209.长度最小的子数组

﹏ヽ暗。殇╰゛Y 2023-10-06 23:18 47阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

**示例 3：**  
输入：target = 11, nums = \[1,1,1,1,1,1,1,1\]  
输出：0

**提示：**  
1 <= target <= 109  
1 <= nums.length <= 105  
1 <= nums\[i\] <= 105

**进阶：**  
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(nlog(n)) 时间复杂度的解法。

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/minimum-size-subarray-sum

## 2.思路 ##

（1）暴力穷举法  
该方法比较容易想到，即使用两层 for 循环来遍历所有的子数组，然后用变量 minLen 来记录其最小长度即可。但是显然该方法的时间复杂度较高，为 O(n2)，并且在 LeetCode 上提交是可能会出现“超出时间限制”的提示！

（2）滑动窗口  
思路参考[本题官方题解][Link 1]。

（3）前缀和\_二分搜索  
如果要设计一个时间复杂度为 O(nlog(n)) 的算法，那么我们可以联想到**线性遍历 + 二分搜索**的组合，即在每趟遍历的过程中使用一次二分搜素，那么其时间复杂度正好为 O(n) \* O(logn) = O(nlogn)。具体步骤如下：

*  构造**前缀和数组 preSum**（长度为 nums.length + 1），即 preSum\[i\] = nums\[0\] + … + nums\[i - 1\]；
 *  那么 **preSum\[j\] - preSum\[i\] 为数组 nums 中连续子数组 nums\[i…j) 的和**，所以我们可将题目理解为**要求返回当 preSum\[j\] - preSum\[i\] ≥ target 时 j - i + 1 的最小值**；
 *  由于数组 nums 中的元素均为正整数，所以数组 preSum 中的元素是单调递增的。当 i 的值固定时，preSum\[j\] - preSum\[i\] 随着 j 的增大而增大，故也是递增的；
 *  所以我们可以使用**二分搜索**来查找满足题目条件的连续子数组的最小长度，同时为了方便理解，我们令 newTarget = target + preSum\[i - 1\]，即要求搜索当 preSum\[j\] ≥ newTarget 时 j - i + 1 的最小值；
 *  这样我们可以在每一次遍历中固定 i （ i 的取值为 \[1, nums.length\]），然后再通过二分搜索 binarySearch(int\[\] preSum, int newTarget) 找出数组 preSum 中第一个大于等于 newTarget 的元素下标 j，并用变量 minLen 记录最小长度 j - i + 1即可。

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public int minSubArrayLen(int target, int[] nums) {
        
            int length = nums.length;
            if (length == 0) {
        
                return 0;
            }
            int minLen = Integer.MAX_VALUE;
            for (int i = 0; i < length; i++) {
        
                int subSum = 0;
                for (int j = i; j < length; j++) {
        
                    subSum += nums[j];
                    if (subSum >= target) {
        
                        minLen = Math.min(j - i + 1, minLen);
                        //数组 nums 中的元素均为正整数，所以 subSum 越加越大，后面的 subSum 肯定都大于等于 target
                        break;
                    }
                }
            }
            return minLen == Integer.MAX_VALUE ? 0 : minLen;
        }
    }

//思路2————滑动窗口
    class Solution {
        
       public int minSubArrayLen(int target, int[] nums) {
        
            int length = nums.length;
            int minLen = Integer.MAX_VALUE;
            int left = 0;
            int right = 0;
            int subSum = 0;
            while (right < length) {
        
                subSum += nums[right];
                right++;
                while (subSum >= target) {
        
                    minLen = Math.min(minLen, right - left);
                    subSum -= nums[left];
                    left++;
                }
            }
            return minLen == Integer.MAX_VALUE ? 0 : minLen;
        }
    }

//思路3————前缀和_二分搜索
    class Solution {
        
        public int minSubArrayLen(int target, int[] nums) {
        
            int length = nums.length;
            int[] preSum = new int[length + 1];
            //计算数组 nums 的累加和
            for (int i = 1; i <= length; i++) {
        
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }
            //minLen 记录和大于等于 target 的连续子数组 [nums[l], nums[l+1], ..., nums[r-1], nums[r] 的最小长度
            int minLen = Integer.MAX_VALUE;
            for (int i = 1; i <= length; i++) {
        
                int newTarget = target + preSum[i - 1];
                int j = binarySearch(preSum, newTarget);
                if (j <= length) {
        
                	//更新 minLen
                    minLen = Math.min(j - i + 1, minLen);
                }
            }
            return minLen == Integer.MAX_VALUE ? 0 : minLen;
        }
        
        /*
        	二分搜索，返回数组 nums 中值为 target 的元素所在的下标
    		如果 target 不在 nums 中，返回值是 nums 中大于等于 target 的最小元素下标
    	*/
        public int binarySearch(int[] nums, int target) {
        
            if (nums == null || nums.length == 0) {
        
                return 0;
            }
            int left = 0, right = nums.length - 1;
            while (left <= right) {
        
                int mid = left + (right - left) / 2;
                if (nums[mid] == target) {
        
                    return mid;
                }
                if (nums[mid] > target) {
        
                    right = mid - 1;
                } else {
        
                    left = mid + 1;
                }
            }
            //若能运行到这里，说明目标值不存在于数组中，此时返回 nums 中大于等于 target 的最小元素索引
            return left;
        }
    }

[Link 1]: https://leetcode.cn/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/