|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
| 3 | +importjava.util.HashMap; |
| 4 | +importjava.util.Map; |
| 5 | + |
3 | 6 | /** |
| 7 | + * 523. Continuous Subarray Sum |
| 8 | + * |
4 | 9 | * Given a list of non-negative numbers and a target integer k, |
5 | 10 | * write a function to check if the array has a continuous subarray of size at least 2 |
6 | 11 | * that sums up to the multiple of k, that is, sums up to n*k where n is also an integer. |
|
21 | 26 |
|
22 | 27 | */ |
23 | 28 | publicclass_523 { |
24 | | -/**TODO: could be optimized to O(n) time and O(k) space, reference: https://discuss.leetcode.com/topic/80793/java-o-n-time-o-k-space*/ |
| 29 | + |
| 30 | +publicbooleancheckSubarraySumOnTimeO1Space(int[]nums,intk) { |
| 31 | +Map<Integer,Integer>map =newHashMap<>(); |
| 32 | +map.put(0, -1); |
| 33 | +intsum =0; |
| 34 | +for (inti =0;i <nums.length;i++) { |
| 35 | +sum +=nums[i]; |
| 36 | +if (k !=0) { |
| 37 | +/**Because if k == 0, sum %= k will throw ArithmeticException.*/ |
| 38 | +sum %=k; |
| 39 | + } |
| 40 | +Integerprev =map.get(sum); |
| 41 | +if (prev !=null) { |
| 42 | +if (i -prev >1) { |
| 43 | +/**This makes sure that it has length at least 2*/ |
| 44 | +returntrue; |
| 45 | + } |
| 46 | + }else { |
| 47 | +map.put(sum,i); |
| 48 | + } |
| 49 | + } |
| 50 | +returnfalse; |
| 51 | + } |
25 | 52 |
|
26 | 53 | publicbooleancheckSubarraySum(int[]nums,intk) { |
27 | 54 | if (nums ==null ||nums.length ==0)returnfalse; |
|