-
Notifications
You must be signed in to change notification settings - Fork 1
/
MinimumSizeSubarraySum.java
68 lines (59 loc) · 2.07 KB
/
MinimumSizeSubarraySum.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package com.leetcode;
import java.util.HashMap;
public class MinimumSizeSubarraySum {
/**
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.
**/
class Solution {
//O(n) - sliding window
public int minSubArrayLen(int s, int[] nums) {
if(nums.length == 0){
return 0;
}
int n = nums.length;
int minLen = n+1;
int sum = 0;
int start = 0;
for(int end = 0 ; end < n ; end++){
sum = nums[end] + sum;
while(sum >= s){
minLen = Math.min(minLen , end - start +1);
sum = sum - nums[start];
start++;//It means that the first index can safely be incremented, since, the minimum subarray starting with this index with sum >= s has been achieved
}
}
if(minLen == n+1){
return 0;
}
return minLen;
}
}
//we need an array min length whose sum == s
class MinimumSizeSubarraySumEqualK {
public int minSubArrayLen(int s, int[] nums) {
HashMap<Integer,Integer> map = new HashMap<>();
int minLen = Integer.MAX_VALUE;
int sum = 0;
// all positive integers so sum value is unique at each location
for(int i = 0 ; i < nums.length; i++){
sum = sum + nums[i];
if(sum == s){
minLen = i+1;//from 0 to this position is an array with sum
}
map.put(sum,i);//sum at each index
}
sum = 0;
for(int i = 0 ; i < nums.length; i++){
sum = sum + nums[i];
if(map.containsKey(sum - s)){
int len = i - map.get(sum-s);
minLen = Math.min(len,minLen);
}
}
if(minLen == Integer.MAX_VALUE) return 0;
return minLen;
}
}
}