Leetcode: Minimum Size Subarray Sum
LeetCode size sum minimum Subarray
2023-09-11 14:14:07 时间
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 0 instead. For 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. click to show more practice. More practice: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
Haven't think about the O(nlogn) solution.
O(n) solution is to maintain a window
1 public class Solution { 2 public int minSubArrayLen(int s, int[] nums) { 3 int minWin = Integer.MAX_VALUE; 4 int l=0, r=0; 5 if (nums==null || nums.length==0) return 0; 6 int sum = 0; 7 while (r < nums.length) { 8 sum += nums[r]; 9 while (sum >= s) { 10 minWin = Math.min(minWin, r-l+1); 11 sum -= nums[l++]; 12 } 13 r++; 14 } 15 return minWin == Integer.MAX_VALUE? 0 : minWin; 17 } 18 }
My solution: shrink as much as possible while maintaining the window always correct
1 public class Solution { 2 public int minSubArrayLen(int s, int[] nums) { 3 int minWin = Integer.MAX_VALUE; 4 int l=0, r=0; 5 if (nums == null || nums.length == 0) return 0; 6 int sum = 0; 7 while (r < nums.length) { 8 sum += nums[r]; 9 while (sum - nums[l] >= s) { 10 sum -= nums[l++]; 11 } 12 if (sum >= s) 13 minWin = Math.min(minWin, r - l + 1); 14 r++; 15 } 16 17 return minWin == Integer.MAX_VALUE? 0 : minWin; 18 } 19 }
相关文章
- Java实现 LeetCode 811 子域名访问计数 (暴力)
- Java实现 LeetCode 733 图像渲染(DFS)
- Java实现 LeetCode 350 两个数组的交集 II(二)
- SQL Server实现 LeetCode 178 分数排名
- Java实现 LeetCode 20 有效的括号
- LeetCode(77):组合
- ( “树” 之 DFS) 226. 翻转二叉树 ——【Leetcode每日一题】
- 【LeetCode-面试算法经典-Java实现】【008-String to Integer (atoi) (字符串转成整数)】
- leetcode 119. Pascal's Triangle II
- 【LeetCode】数组中第K大的元素