Skip to content

Commit 26e14a9

Browse files
fishercoder1534fishercoder1534
committed
refactor 523
1 parent ae861eb commit 26e14a9

File tree

2 files changed

+78
-77
lines changed

2 files changed

+78
-77
lines changed

‎src/main/java/com/fishercoder/solutions/_523.java

Lines changed: 54 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -27,68 +27,73 @@
2727
*/
2828
public class _523 {
2929

30-
/**reference: https://discuss.leetcode.com/topic/80793/java-o-n-time-o-k-space/20
31-
*
32-
* "The reason we use modulus is:
33-
* (a+(n*x))%x is same as (a%x)
34-
* e.g. in case of the array [23,2,6,4,7] the running sum is [23,25,31,35,42]
35-
* and the remainders are [5,1,1,5,0].
36-
* We got reminder 5 at index 0 and at index 3.
37-
* That means, in between these two indexes we must have added a number which is multiple of the k.
38-
* Hope this clarifies your doubt :)"*/
39-
public boolean checkSubarraySumOnTimeO1Space(int[] nums, int k) {
40-
Map<Integer, Integer> map = new HashMap<>();
41-
map.put(0, -1);
42-
int sum = 0;
43-
for (int i = 0; i < nums.length; i++) {
44-
sum += nums[i];
45-
if (k != 0) {
46-
/**Because if k == 0, sum %= k will throw ArithmeticException.*/
47-
sum %= k;
48-
}
49-
Integer prev = map.get(sum);
50-
if (prev != null) {
51-
if (i - prev > 1) {
52-
/**This makes sure that it has length at least 2*/
53-
return true;
30+
public static class Solution1 {
31+
/**
32+
* reference: https://discuss.leetcode.com/topic/80793/java-o-n-time-o-k-space/20
33+
* "The reason we use modulus is:
34+
* (a+(n*x))%x is same as (a%x)
35+
* e.g. in case of the array [23,2,6,4,7] the running sum is [23,25,31,35,42]
36+
* and the remainders are [5,1,1,5,0].
37+
* We got reminder 5 at index 0 and at index 3.
38+
* That means, in between these two indexes we must have added a number which is multiple of the k.
39+
* Hope this clarifies your doubt :)"
40+
*/
41+
public boolean checkSubarraySum(int[] nums, int k) {
42+
Map<Integer, Integer> map = new HashMap<>();
43+
map.put(0, -1);
44+
int sum = 0;
45+
for (int i = 0; i < nums.length; i++) {
46+
sum += nums[i];
47+
if (k != 0) {
48+
/**Because if k == 0, sum %= k will throw ArithmeticException.*/
49+
sum %= k;
50+
}
51+
Integer prev = map.get(sum);
52+
if (prev != null) {
53+
if (i - prev > 1) {
54+
/**This makes sure that it has length at least 2*/
55+
return true;
56+
}
57+
} else {
58+
map.put(sum, i);
5459
}
55-
} else {
56-
map.put(sum, i);
5760
}
61+
return false;
5862
}
59-
return false;
6063
}
6164

62-
public boolean checkSubarraySum(int[] nums, int k) {
63-
if (nums == null || nums.length == 0) {
64-
return false;
65-
}
65+
public static class Solution2 {
66+
public boolean checkSubarraySum(int[] nums, int k) {
67+
if (nums == null || nums.length == 0) {
68+
return false;
69+
}
6670

67-
//Two continuous zeroes will form a subarray of length 2 with sum 0, 0*k = 0 will always be true
68-
for (int i = 0; i < nums.length - 1; i++) {
69-
if (nums[i] == 0 && nums[i + 1] == 0) {
70-
return true;
71+
//Two continuous zeroes will form a subarray of length 2 with sum 0, 0*k = 0 will always be true
72+
for (int i = 0; i < nums.length - 1; i++) {
73+
if (nums[i] == 0 && nums[i + 1] == 0) {
74+
return true;
75+
}
7176
}
72-
}
7377

74-
//then k cannot be zero any more
75-
if (k == 0 || nums.length < 2) {
76-
return false;
77-
}
78+
//then k cannot be zero any more
79+
if (k == 0 || nums.length < 2) {
80+
return false;
81+
}
7882

79-
int[] preSums = new int[nums.length + 1];
80-
for (int i = 1; i <= nums.length; i++) {
81-
preSums[i] = preSums[i - 1] + nums[i - 1];
82-
}
83+
int[] preSums = new int[nums.length + 1];
84+
for (int i = 1; i <= nums.length; i++) {
85+
preSums[i] = preSums[i - 1] + nums[i - 1];
86+
}
8387

84-
for (int i = 1; i <= nums.length; i++) {
85-
for (int j = 0; j < i - 1; j++) {
86-
if ((preSums[i] - preSums[j]) % k == 0) {
87-
return true;
88+
for (int i = 1; i <= nums.length; i++) {
89+
for (int j = 0; j < i - 1; j++) {
90+
if ((preSums[i] - preSums[j]) % k == 0) {
91+
return true;
92+
}
8893
}
8994
}
95+
return false;
9096
}
91-
return false;
9297
}
9398

9499
}

‎src/test/java/com/fishercoder/_523Test.java

Lines changed: 24 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -1,116 +1,112 @@
11
package com.fishercoder;
22

33
import com.fishercoder.solutions._523;
4-
import org.junit.Before;
54
import org.junit.BeforeClass;
65
import org.junit.Test;
76

87
import static junit.framework.Assert.assertEquals;
98

109
public class _523Test {
11-
private static _523 test;
10+
private static _523.Solution1 solution1;
11+
private static _523.Solution2 solution2;
1212
private static boolean expected;
13-
private static boolean actual;
1413
private static int[] nums;
1514
private static int k;
1615

1716
@BeforeClass
1817
public static void setup() {
19-
test = new _523();
20-
}
21-
22-
@Before
23-
public void setupForEachTest() {
18+
solution1 = new _523.Solution1();
19+
solution2 = new _523.Solution2();
2420
}
2521

2622
@Test
2723
public void test1() {
2824
nums = new int[]{23, 2, 4, 6, 7};
2925
expected = true;
3026
k = 6;
31-
actual = test.checkSubarraySum(nums, k);
32-
assertEquals(expected, actual);
27+
assertEquals(expected, solution1.checkSubarraySum(nums, k));
28+
assertEquals(expected, solution2.checkSubarraySum(nums, k));
3329
}
3430

3531
@Test
3632
public void test2() {
3733
nums = new int[]{23, 2, 6, 4, 7};
3834
expected = true;
3935
k = 6;
40-
actual = test.checkSubarraySum(nums, k);
41-
assertEquals(expected, actual);
36+
assertEquals(expected, solution1.checkSubarraySum(nums, k));
37+
assertEquals(expected, solution2.checkSubarraySum(nums, k));
4238
}
4339

4440
@Test
4541
public void test3() {
4642
nums = new int[]{23, 2, 6, 4, 7};
4743
expected = false;
4844
k = 0;
49-
actual = test.checkSubarraySum(nums, k);
50-
assertEquals(expected, actual);
45+
assertEquals(expected, solution1.checkSubarraySum(nums, k));
46+
assertEquals(expected, solution2.checkSubarraySum(nums, k));
5147
}
5248

5349
@Test
5450
public void test4() {
5551
nums = new int[]{0, 1, 0};
5652
expected = false;
5753
k = 0;
58-
actual = test.checkSubarraySum(nums, k);
59-
assertEquals(expected, actual);
54+
assertEquals(expected, solution1.checkSubarraySum(nums, k));
55+
assertEquals(expected, solution2.checkSubarraySum(nums, k));
6056
}
6157

6258
@Test
6359
public void test5() {
6460
nums = new int[]{0, 0};
6561
expected = true;
6662
k = 0;
67-
actual = test.checkSubarraySum(nums, k);
68-
assertEquals(expected, actual);
63+
assertEquals(expected, solution1.checkSubarraySum(nums, k));
64+
assertEquals(expected, solution2.checkSubarraySum(nums, k));
6965
}
7066

7167
@Test
7268
public void test6() {
7369
nums = new int[]{1, 1};
7470
expected = true;
7571
k = 2;
76-
actual = test.checkSubarraySum(nums, k);
77-
assertEquals(expected, actual);
72+
assertEquals(expected, solution1.checkSubarraySum(nums, k));
73+
assertEquals(expected, solution2.checkSubarraySum(nums, k));
7874
}
7975

8076
@Test
8177
public void test7() {
8278
nums = new int[]{0};
8379
expected = false;
8480
k = -1;
85-
actual = test.checkSubarraySum(nums, k);
86-
assertEquals(expected, actual);
81+
assertEquals(expected, solution1.checkSubarraySum(nums, k));
82+
assertEquals(expected, solution2.checkSubarraySum(nums, k));
8783
}
8884

8985
@Test
9086
public void test8() {
9187
nums = new int[]{23, 2, 4, 6, 7};
9288
expected = true;
9389
k = -6;
94-
actual = test.checkSubarraySum(nums, k);
95-
assertEquals(expected, actual);
90+
assertEquals(expected, solution1.checkSubarraySum(nums, k));
91+
assertEquals(expected, solution2.checkSubarraySum(nums, k));
9692
}
9793

9894
@Test
9995
public void test9() {
10096
nums = new int[]{1, 2, 3};
10197
expected = false;
10298
k = 4;
103-
actual = test.checkSubarraySum(nums, k);
104-
assertEquals(expected, actual);
99+
assertEquals(expected, solution1.checkSubarraySum(nums, k));
100+
assertEquals(expected, solution2.checkSubarraySum(nums, k));
105101
}
106102

107103
@Test
108104
public void test10() {
109105
nums = new int[]{5, 2, 4};
110106
expected = false;
111107
k = 5;
112-
actual = test.checkSubarraySum(nums, k);
113-
assertEquals(expected, actual);
108+
assertEquals(expected, solution1.checkSubarraySum(nums, k));
109+
assertEquals(expected, solution2.checkSubarraySum(nums, k));
114110
}
115111

116112
}

0 commit comments

Comments
 (0)