leetcode面试经典150题——30 长度最小的子数组

题目：长度最小的子数组

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

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

示例 1：

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

leetcode链接

方法一：滑动窗口
滑动窗口有两种：一种是固定大小的窗口，另一种是动态大小的窗口，而本题要求长度最小的子数组，所以应该用动态大小的窗口，滑动窗口基于双指针的思想：
我们定义两个指针left和right表示窗口的两端，定义一个minLen变量表示最端短的长度，初始时指针都指向0，此时如果窗口内的数之和小于目标数target，那么right指针右移，窗口变大，相反如果窗口内的数之和大于目标数target，那么更新minLen,并且移动left指针，直到窗口内的数之和小于目标数target为止。最后遍历完数组，minLen即为长度最小的子数组
时间复杂度；o(n)
空间复杂度：o(1)

int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int minLen = n+1;int left = 0,right = 0;int sum = 0;while(right<n){sum+=nums[right];while(sum>=target){minLen = min(minLen,right-left+1);sum-=nums[left];left++;}right++;}//如果minLen没有更新过，即为不存在满足条件的子数组，返回0return minLen==n+1?0:minLen;}

方法二：暴力法
我们枚举数组中的每一个元素为子数组的起始元素，然后找到从枚举的元素开始满足条件的最小子数组的长度，再维护最小的子数组长度，即可找到答案。
时间复杂度：o(n²)
空间复杂度：o(1)

int minSubArrayLen(int s, vector<int>& nums) {int n = nums.size();if (n == 0) {return 0;}int ans = INT_MAX;for (int i = 0; i < n; i++) {int sum = 0;for (int j = i; j < n; j++) {sum += nums[j];if (sum >= s) {ans = min(ans, j - i + 1);break;}}}return ans == INT_MAX ? 0 : ans;}

方法三：前缀和+二分查找
暴力法中枚举子数组起始元素的时间复杂度为o(n),找到最小子数组的时间复杂度为o(n),此时我们考虑优化寻找最小子数组的时间，注意到我们给定的数组的所有的元素都是大于0的，那么我们每一个元素的前缀和都是递增的，因此我们可以利用二分查找来查找最小子数组，如果我们枚举第i个元素为最小子数组的起始元素，那么我们二分查找的元素可以变为target+i的前缀和，而此时找到的目标元素的前缀和-i的前缀和 = target，因此我们找到的元素即为最短子数组的末尾，然后我们再维护最短的一个长度
时间复杂度：o(nlogn) 二分查找的时间复杂度为logn
空间复杂度：o(n) 存储前缀和的空间为o(n)
注意：注意二分查找时的left和right指针的取值

int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int minLen = n+1,mid = 0;vector<int> sum(n+1,0);//sum[i]表示前i个数之和 for(int i=1;i<=n;i++){sum[i] = sum[i-1]+nums[i-1];}for(int i=1;i<=n;i++){//枚举每个元素为子数组的起始元素//注意i为第i个元素，而第i个元素的下标为i-1int tag = target+sum[i-1];//这里的left和right表示的为第几个元素，由于sum[i]为第i个元素的前缀和int left = i,right = n;while(left<right){mid = (left+right)/2;if(tag>sum[mid]){left = mid+1;}else{//我们要找的数为大于等于tag，所以right=mid，而不是mid-1right = mid;}}if(sum[left]>=tag){minLen = min(left-i+1,minLen);}}return minLen==n+1?0:minLen;
}