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

Commita17a0c9

Browse files
refactor 523
1 parent02c14f6 commita17a0c9

File tree

2 files changed

+15
-3
lines changed

2 files changed

+15
-3
lines changed

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

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8,17 +8,17 @@ public class _523 {
88
publicstaticclassSolution1 {
99
/**
1010
* reference: https://discuss.leetcode.com/topic/80793/java-o-n-time-o-k-space/20
11-
* "The reason we usemodulus is:
11+
* "The reason we usemodulo is:
1212
* (a+(n*x))%x is same as (a%x)
13-
* e.g. in case of the array [23,2,6,4,7] the running sum is [23,25,31,35,42]
13+
* e.g. in case of the array [23,2,6,4,7]and k = 6the running sum is [23,25,31,35,42]
1414
* and the remainders are [5,1,1,5,0].
1515
* We got reminder 5 at index 0 and at index 3.
1616
* That means, in between these two indexes we must have added a number which is multiple of the k.
1717
* Hope this clarifies your doubt :)"
1818
*/
1919
publicbooleancheckSubarraySum(int[]nums,intk) {
2020
Map<Integer,Integer>map =newHashMap<>();
21-
map.put(0, -1);
21+
map.put(0, -1);//this line is critical to mark the beginning of the prefix sum, so that next time, when we encounter a running sum of zero, we know that's the answer, see test case 11
2222
intsum =0;
2323
for (inti =0;i <nums.length;i++) {
2424
sum +=nums[i];
@@ -41,6 +41,9 @@ public boolean checkSubarraySum(int[] nums, int k) {
4141
}
4242

4343
publicstaticclassSolution2 {
44+
/**
45+
* O(n^2), this will time out on LeetCode.
46+
*/
4447
publicbooleancheckSubarraySum(int[]nums,intk) {
4548
if (nums ==null ||nums.length ==0) {
4649
returnfalse;

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

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -109,4 +109,13 @@ public void test10() {
109109
assertEquals(expected,solution2.checkSubarraySum(nums,k));
110110
}
111111

112+
@Test
113+
publicvoidtest11() {
114+
nums =newint[]{23,2,4,6,6};
115+
expected =true;
116+
k =7;
117+
assertEquals(expected,solution1.checkSubarraySum(nums,k));
118+
assertEquals(expected,solution2.checkSubarraySum(nums,k));
119+
}
120+
112121
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp