Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit26e14a9

Browse files
refactor 523
1 parentae861eb commit26e14a9

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
publicclass_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-
publicbooleancheckSubarraySumOnTimeO1Space(int[]nums,intk) {
40-
Map<Integer,Integer>map =newHashMap<>();
41-
map.put(0, -1);
42-
intsum =0;
43-
for (inti =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-
Integerprev =map.get(sum);
50-
if (prev !=null) {
51-
if (i -prev >1) {
52-
/**This makes sure that it has length at least 2*/
53-
returntrue;
30+
publicstaticclassSolution1 {
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+
publicbooleancheckSubarraySum(int[]nums,intk) {
42+
Map<Integer,Integer>map =newHashMap<>();
43+
map.put(0, -1);
44+
intsum =0;
45+
for (inti =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+
Integerprev =map.get(sum);
52+
if (prev !=null) {
53+
if (i -prev >1) {
54+
/**This makes sure that it has length at least 2*/
55+
returntrue;
56+
}
57+
}else {
58+
map.put(sum,i);
5459
}
55-
}else {
56-
map.put(sum,i);
5760
}
61+
returnfalse;
5862
}
59-
returnfalse;
6063
}
6164

62-
publicbooleancheckSubarraySum(int[]nums,intk) {
63-
if (nums ==null ||nums.length ==0) {
64-
returnfalse;
65-
}
65+
publicstaticclassSolution2 {
66+
publicbooleancheckSubarraySum(int[]nums,intk) {
67+
if (nums ==null ||nums.length ==0) {
68+
returnfalse;
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 (inti =0;i <nums.length -1;i++) {
69-
if (nums[i] ==0 &&nums[i +1] ==0) {
70-
returntrue;
71+
//Two continuous zeroes will form a subarray of length 2 with sum 0, 0*k = 0 will always be true
72+
for (inti =0;i <nums.length -1;i++) {
73+
if (nums[i] ==0 &&nums[i +1] ==0) {
74+
returntrue;
75+
}
7176
}
72-
}
7377

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

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

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

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

33
importcom.fishercoder.solutions._523;
4-
importorg.junit.Before;
54
importorg.junit.BeforeClass;
65
importorg.junit.Test;
76

87
importstaticjunit.framework.Assert.assertEquals;
98

109
publicclass_523Test {
11-
privatestatic_523test;
10+
privatestatic_523.Solution1solution1;
11+
privatestatic_523.Solution2solution2;
1212
privatestaticbooleanexpected;
13-
privatestaticbooleanactual;
1413
privatestaticint[]nums;
1514
privatestaticintk;
1615

1716
@BeforeClass
1817
publicstaticvoidsetup() {
19-
test =new_523();
20-
}
21-
22-
@Before
23-
publicvoidsetupForEachTest() {
18+
solution1 =new_523.Solution1();
19+
solution2 =new_523.Solution2();
2420
}
2521

2622
@Test
2723
publicvoidtest1() {
2824
nums =newint[]{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
publicvoidtest2() {
3733
nums =newint[]{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
publicvoidtest3() {
4642
nums =newint[]{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
publicvoidtest4() {
5551
nums =newint[]{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
publicvoidtest5() {
6460
nums =newint[]{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
publicvoidtest6() {
7369
nums =newint[]{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
publicvoidtest7() {
8278
nums =newint[]{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
publicvoidtest8() {
9187
nums =newint[]{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
publicvoidtest9() {
10096
nums =newint[]{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
publicvoidtest10() {
109105
nums =newint[]{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)
[8]ページ先頭
©2009-2025 Movatter.jp