leetcode209. Minimum Size Subarray Sum

本文主要是介绍leetcode209. Minimum Size Subarray Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

Given an array of positive integers nums and a positive integer target, return the minimal length of a
subarray
whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

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

Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

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方

也可以用双指针滑动窗口来进行
时间复杂度是n

但是这题还提供了一个深入的跟进思考
建议再想一个时间复杂度是nlogn的方法

暴力解法在leetcode中会超时

该题需要考虑边界条件以及双循环变量使用时数组的边界越界问题

暴力解法

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int max = 0;for(int i = 0; i < nums.size(); i++){max += nums[i];}if(target > max)return 0;else if(target == max)return nums.size();else{int subl;  // minimum is 1int sum;int minl = 100000;for(int i = 0; i < nums.size(); i++){int j = i;subl = 1;sum = 0;sum += nums[i];while(sum < target && j < nums.size()){if(j == nums.size()-1)break;j++;sum += nums[j];subl++;}if(sum >= target){if(subl == 1)return 1;if(subl <= minl)minl = subl;}}return minl;}}
};

双指针滑动窗口解法

这篇关于leetcode209. Minimum Size Subarray Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---