首页 > 代码库 > Minimum Size Subarray Sum
Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn‘t one, return -1 instead.
Example
Given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.
Challenge 
View Code
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
Analyse: Two pointers. O(n)
Runtime: 203ms
1 class Solution { 2 public: 3 /** 4 * @param nums: a vector of integers 5 * @param s: an integer 6 * @return: an integer representing the minimum size of subarray 7 */ 8 int minimumSize(vector<int> &nums, int s) { 9 // write your code here10 // mark left, set right as left + 111 // move right until sum of nums[left...right] >= s12 // update the min length and let left move one position13 // if current sum >= s update min length and keep move left14 // if current sum < s move right one position15 16 if (nums.empty()) return -1;17 int left = 0, right = 1;18 int minSize = INT_MAX, tempSum = nums[left];19 if (tempSum > s) return 1;20 while (left < nums.size() && right < nums.size()) {21 tempSum += nums[right];22 while (tempSum >= s) {23 minSize = min(minSize, right - left + 1);24 tempSum -= nums[left];25 left++;26 }27 if (tempSum < s) {28 right++;29 }30 }31 return minSize == INT_MAX ? -1 : minSize;32 }33 };
Analyse: Brute force. O(n^2)
Runtime: 605ms
1 class Solution { 2 public: 3 /** 4 * @param nums: a vector of integers 5 * @param s: an integer 6 * @return: an integer representing the minimum size of subarray 7 */ 8 int minimumSize(vector<int> &nums, int s) { 9 // write your code here10 if (nums.empty()) return -1;11 12 int result = INT_MAX;13 for (int i = 0; i < nums.size(); i++) {14 int tempSum = nums[i];15 if (tempSum >= s) return 1;16 for (int j = i + 1; j < nums.size(); j++) {17 tempSum += nums[j];18 if (tempSum >= s) {19 result = min(result, j - i + 1);20 break;21 }22 }23 }24 return result == INT_MAX ? -1 : result;25 }26 };
Minimum Size Subarray Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。