摘要:做一個窗口,滿足的左界到右界的距離最小值為所求。循環的約束條件要注意,不要遺漏不能超過的長度,但可以等于,因為存在所有元素之和為的極端情況。在時,先更新窗口為當前循環后的最小值,減去最左元素,指針后移。
Problem
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.
ExampleGiven the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.
ChallengeIf you have figured out the O(n) solution, try coding another solution of which the time complexity is O(nlogn).
Note做一個窗口minsize,滿足sum >= s的左界到右界的距離最小值為所求。while循環的約束條件要注意,不要遺漏:right不能超過nums[]的長度,但可以等于,因為存在nums[]所有元素之和為s的極端情況。
在sum < s時,sum加上右指針的元素,同時right指針后移,但是注意當right = nums.length時,sum不能加(元素不存在!),所以sum += nums[right]要加限制條件。
在sum >= s時,先更新窗口為當前循環后的最小值,減去最左元素,left指針后移。
public class Solution { public int minimumSize(int[] nums, int s) { if (nums == null) return -1; int left = 0, right = 0, sum = 0, minsize = Integer.MAX_VALUE; while (right <= nums.length && left <= right) { if (sum < s) { if (right < nums.length) { sum += nums[right]; } right++; } else { minsize = Math.min(minsize, right - left); sum -= nums[left]; left++; } } return minsize <= nums.length ? minsize : -1; } }
Binary Search:
http://www.jyuan92.com/blog/leetcode-min...
public class Solution { public int minimumSize(int[] nums, int s) { if (nums == null || nums.length == 0) return -1; int[] sum = new int[nums.length+1]; int minsize = Integer.MAX_VALUE; for (int i = 0; i < nums.length; i++) { sum[i+1] = sum[i] + nums[i]; if (sum[i+1] >= s) { int left = helper(sum, sum[i+1]-s, 0, i+1); minsize = Math.min(minsize, i+1-left); } } return minsize > nums.length ? -1 : minsize; } public int helper(int[] A, int target, int start, int end) { while (start + 1 < end) { int mid = start + (end - start) / 2; if (A[mid] < target) start = mid; else end = mid; //A[mid] = target is in this branch } if (A[end] <= target) return end;//Make sure return the same brunch //---->end, when A[end] = target else return start; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/65523.html
摘要:雙指針復雜度時間空間思路我們用兩個指針維護一個窗口,保證這個窗口的內的和是小于目標數的。如果和仍小于目標數,則將窗口右邊界右移。另外,如果左邊界大于右邊界時,說明最短子串的長度已經小于等于,我們就不用再查找了。 Minimum Size Subarray Sum Given an array of n positive integers and a positive integer ...
Problem 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 isnt one, return 0 instead. Example: Input: s =...
摘要:如果不存在符合條件的連續子數組,返回。示例輸入輸出解釋子數組是該條件下的長度最小的連續子數組。截取從索引到索引的數組,該數組之和若小于,則繼續后移,直到大于等于。記錄與差值返回的目標數。之后后移一位繼續刷新新數組。 公眾號: 愛寫bug(ID:icodebugs)作者:愛寫bug 給定一個含有 n 個正整數的數組和一個正整數 s ,找出該數組中滿足其和 ≥ s 的長度最小的連續子數組...
摘要:如果不存在符合條件的連續子數組,返回。示例輸入輸出解釋子數組是該條件下的長度最小的連續子數組。截取從索引到索引的數組,該數組之和若小于,則繼續后移,直到大于等于。記錄與差值返回的目標數。之后后移一位繼續刷新新數組。 公眾號: 愛寫bug(ID:icodebugs)作者:愛寫bug 給定一個含有 n 個正整數的數組和一個正整數 s ,找出該數組中滿足其和 ≥ s 的長度最小的連續子數組...
摘要:如果不存在符合條件的連續子數組,返回。示例輸入輸出解釋子數組是該條件下的長度最小的連續子數組。截取從索引到索引的數組,該數組之和若小于,則繼續后移,直到大于等于。記錄與差值返回的目標數。之后后移一位繼續刷新新數組。 算法是一個程序的靈魂 公眾號:愛寫bug(ID:icodebugs)作者:愛寫bug 給定一個含有 n 個正整數的數組和一個正整數 s ,找出該數組中滿足其和 ≥ s 的...
閱讀 1164·2021-09-10 10:51
閱讀 896·2019-08-30 15:53
閱讀 2724·2019-08-30 12:50
閱讀 976·2019-08-30 11:07
閱讀 1990·2019-08-30 10:50
閱讀 3598·2019-08-29 18:47
閱讀 1308·2019-08-29 18:44
閱讀 1599·2019-08-29 17:01