-
Notifications
You must be signed in to change notification settings - Fork 88
/
ContinuousSubarraySum523.java
83 lines (76 loc) · 2.23 KB
/
ContinuousSubarraySum523.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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
* Given a list of non-negative numbers and a target integer k, write a
* function to check if the array has a continuous subarray of size at least 2
* that sums up to the multiple of k, that is, sums up to n*k where n is also
* an integer.
*
* Example 1:
* Input: [23, 2, 4, 6, 7], k=6
* Output: True
* Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up
* to 6.
*
* Example 2:
* Input: [23, 2, 6, 4, 7], k=6
* Output: True
* Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5
* and sums up to 42.
*
* Note:
* The length of the array won't exceed 10,000.
* You may assume the sum of all the numbers is in the range of a signed
* 32-bit integer.
*
*/
public class ContinuousSubarraySum523 {
public boolean checkSubarraySum(int[] nums, int k) {
if (k == 0) return kIsZero(nums);
return kIsNotZero(nums, k);
}
public boolean kIsNotZero(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int sum = 0;
for (int i=0; i<nums.length; i++) {
sum += nums[i];
int mod = sum % k;
if (map.containsKey(mod)) {
if (i - map.get(mod) >= 2) return true;
} else {
map.put(mod, i);
}
}
return false;
}
public boolean kIsZero(int[] nums) {
int count = 0;
for (int i=0; i<nums.length; i++) {
if (nums[i] == 0) {
count++;
if (count >= 2) return true;
} else {
count = 0;
}
}
return false;
}
/**
* https://leetcode.com/problems/continuous-subarray-sum/solution/
*/
public boolean checkSubarraySum2(int[] nums, int k) {
int sum = 0;
HashMap < Integer, Integer > map = new HashMap < > ();
map.put(0, -1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (k != 0)
sum = sum % k;
if (map.containsKey(sum)) {
if (i - map.get(sum) > 1)
return true;
} else
map.put(sum, i);
}
return false;
}
}