目录

1，题目描述

英文描述

中文描述

2，解题思路

方法一：双指针法O(N)

方法二：前缀和+二分查找O(NlogN)

3，AC代码

方法一：双指针法O(N)

C++

Java

方法二：前缀和+二分查找O(NlogN)

C++ 

Java

4，解题过程

第一博

第二搏

第三搏

---

1，题目描述

原题链接209. 长度最小的子数组

英文描述

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example: 

Input: s = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n). 

中文描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

 

示例：

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

进阶：

如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2，解题思路

双指针法具体实现以及O(NlogN)解法参考@力扣官方题解【长度最小的子数组】

方法一：双指针法O(N)

首先注意到题目给定的条件：正整数数组，连续子数组累加和>=s。

由于是正整数数组，所以左边界相同时，右边界内包含的数字越多，其和越大，因而可以通过左右指针限定子数组范围，sum表示范围内的整数和；

sum < s 时：右指针右移，sum增大，更新sum += nums[right]；sum >= s 时：左指针右移，符合条件，更新结果ans = min(ans, right - left  + 1) ，sum减小，更新sum -= nums[left]；

当右指针到达数组右边界时，算法结束；

方法二：前缀和+二分查找O(NlogN)

构造一个前缀和数组sums，sums[i] = nums[0] + nums[1] + ···+ nums[i - 1]；

以sums[i] + s 为目标值target，由于sums为递增的，可以通过二分查找，找到大于等于target的第一个位置；

 

3，AC代码

方法一：双指针法O(N)

C++

class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int left = 0, right = 0, sum = 0, ans = INT_MAX, n = nums.size(); while(right < n) { sum += nums[right]; while(sum >= s) { ans = min(ans, right - left + 1); sum -= nums[left]; left++; } right++; } return ans == INT_MAX ? 0 : ans; // 当答案不存在（数组为空，或无符合条件的子数组）时 返回0 } };

Java

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

方法二：前缀和+二分查找O(NlogN)

C++ 

class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int n = nums.size(), ans = INT_MAX; vector<int> sums(n + 1, 0); for(int i = 1; i <= n; i++) { sums[i] += sums[i - 1] + nums[i - 1]; } for(int i = 1; i <= n; i++) { int target = sums[i - 1] + s; auto bound = lower_bound(sums.begin(), sums.end(), target); if(bound != sums.end()) { ans = min(ans, (int)(bound - sums.begin()) - (i - 1)); } } return ans == INT_MAX ? 0 : ans; } };

Java

关于Arrays.binarySearch返回值的问题可以看这里（参考@别一直流浪【关于binarySearch返回值为负数】）

边界确定可能有点繁琐，慢慢捋一捋吧╮(╯▽╰)╭

class Solution { public int minSubArrayLen(int s, int[] nums) { int n = nums.length, 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++) { int target = sums[i - 1] + s; int bound = Arrays.binarySearch(sums, target); if(bound < 0) { // 说明未找到target准确位置 bound = -bound - 1; // 但是可以确定大于target的第一个元素位置 } if(bound <= n) { // 保证未越界 ans = Math.min(ans, bound - i + 1); } } return ans == Integer.MAX_VALUE ? 0 : ans; } }

4，解题过程

第一博

由于数组全为正数，故采用双指针的方法，sum记录总和，ans记录区间长度；

sum<s，右指针right右移，更新sum += nums[right]，使其增大。sum>=s，左指针left右移，更新sum -= nums[left]，使其减小，并且更新ans；

class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int left = -1, right = -1, sum = 0, ans = INT_MAX; if(nums.size() == 0) return 0; // 处理数组为空的情况 while(true) { if(sum < s) { if(right == nums.size() - 1) break; // 已到达右边界 right++; sum += nums[right]; } else { ans = min(ans, right - left); if(ans == 1) return 1; // 答案不可能小于1 left++; sum -= nums[left]; } } return ans == INT_MAX ? 0 : ans; // 当不存在答案时 返回0 } };

时间复杂度O(N)，空间复杂度O(1)。然而测试的效果差强人意(T_T)

第二搏

官方给出的解答中也有双指针的解法，运行起来效率更高

class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int n = nums.size(); if (n == 0) { return 0; } int ans = INT_MAX; int start = 0, end = 0; int sum = 0; while (end < n) { sum += nums[end]; while (sum >= s) { ans = min(ans, end - start + 1); sum -= nums[start]; start++; } end++; } return ans == INT_MAX ? 0 : ans; } };

对比一下，可以很容易看出，第一博中的代码有几点比较耗时：

指针移动效率。最外层的while，每次循环只能移动一次左/右指针，而官方解法中，外层while内左指针可以连续多次移动；处理逻辑较为复杂。较多的分支语句貌似可以减少某些测试用例的耗时，但对大部分用例来说，只是增加了判断的负担；

第一博中只声明了4个变量，官方解答中声明了5个变量，然而官方解答占用空间却更少。难道是过多的分支判断占用了更多的临时空间？欢迎有想法的同学在评论区讨论o(*￣▽￣*)ブ

第三搏

题目中还要求，能否给出一个O(NlogN)的解法。官方给出了一个解题思路：前缀和+二分查找；

通过遍历一边数组，获得前缀和数组（每个位置i，存放nums[0, i-1]的元素之和），这样给定任意两个位置i，j（i<j）就可以立刻计算出从i到j-1之间的元素之和；借助于前缀和数组，再次遍历数组，每到达一个位置i，以其为左边界，对剩余的数组进行二分查找，找到距i最近的bound，使得nums[bound] - nums[i] >= s；

时间O(NlogN)，空间O(N)；