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

Commit5f38e99

Browse files
[LEET-523] add 523
1 parent5e7102e commit5f38e99

File tree

3 files changed

+120
-0
lines changed

3 files changed

+120
-0
lines changed

‎leetcode-algorithms/README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919
|530|[Minimum Absolute Difference in BST](https://leetcode.com/problems/minimum-absolute-difference-in-bst/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/MinimumAbsoluteDifferenceinBST.java) | O(n) |O(n) | Easy| DFS
2020
|529|[Minesweeper](https://leetcode.com/problems/minesweeper/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/Minesweeper.java) | O(m*n) |O(k) | Medium | BFS
2121
|526|[Beautiful Arrangement](https://leetcode.com/problems/beautiful-arrangement/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/BeautifulArrangement.java) | O(n) |O(h) | Medium | Backtracking
22+
|523|[Continuous Subarray Sum](https://leetcode.com/problems/continuous-subarray-sum/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/ContinuousSubarraySum.java)| O(n^2)|O(n)| Medium|
2223
|520|[Detect Capital](https://leetcode.com/problems/detect-capital/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/DetectCapital.java)| O(n)|O(1)| Easy|
2324
|515|[Find Largest Value in Each Tree Row](https://leetcode.com/problems/find-largest-value-in-each-tree-row/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/FindLargestValueinEachTreeRow.java) | O(n) |O(k) | Medium| BFS
2425
|513|[Find Bottom Left Tree Value](https://leetcode.com/problems/find-bottom-left-tree-value/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/FindBottomLeftValue.java) | O(n) |O(k) | Medium| BFS
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
packagecom.stevesun.solutions;
2+
3+
/**
4+
* 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.
5+
6+
Example 1:
7+
Input: [23, 2, 4, 6, 7], k=6
8+
Output: True
9+
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
10+
11+
Example 2:
12+
Input: [23, 2, 6, 4, 7], k=6
13+
Output: True
14+
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.
15+
16+
Note:
17+
The length of the array won't exceed 10,000.
18+
You may assume the sum of all the numbers is in the range of a signed 32-bit integer.
19+
20+
*/
21+
publicclassContinuousSubarraySum {
22+
//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
23+
24+
publicbooleancheckSubarraySum(int[]nums,intk) {
25+
if (nums ==null ||nums.length ==0)returnfalse;
26+
27+
//Two continuous zeroes will form a subarray of length 2 with sum 0, 0*k = 0 will always be true
28+
for (inti =0;i <nums.length-1;i++) {
29+
if (nums[i] ==0 &&nums[i+1] ==0)returntrue;
30+
}
31+
32+
//then k cannot be zero any more
33+
if (k ==0)returnfalse;
34+
35+
int[]preSums =newint[nums.length];
36+
preSums[0] =nums[0];
37+
for (inti =1;i <nums.length;i++) {
38+
preSums[i] =preSums[i-1] +nums[i];
39+
}
40+
41+
for (inti =1;i <nums.length;i++) {
42+
for (intj =0;j <=i-1;j++) {
43+
if ((preSums[i] -nums[j]) %k ==0)returntrue;
44+
}
45+
}
46+
returnfalse;
47+
}
48+
49+
}
Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
packagecom.stevesun;
2+
3+
importcom.stevesun.solutions.ContinuousSubarraySum;
4+
importorg.junit.Before;
5+
importorg.junit.BeforeClass;
6+
importorg.junit.Test;
7+
8+
importstaticjunit.framework.Assert.assertEquals;
9+
10+
publicclassContinuousSubarraySumTest {
11+
privatestaticContinuousSubarraySumtest;
12+
privatestaticbooleanexpected;
13+
privatestaticbooleanactual;
14+
privatestaticint[]nums;
15+
privatestaticintk;
16+
17+
@BeforeClass
18+
publicstaticvoidsetup(){
19+
test =newContinuousSubarraySum();
20+
}
21+
22+
@Before
23+
publicvoidsetupForEachTest(){}
24+
25+
@Test
26+
publicvoidtest1(){
27+
nums =newint[]{23,2,4,6,7};
28+
expected =true;
29+
k =6;
30+
actual =test.checkSubarraySum(nums,k);
31+
assertEquals(expected,actual);
32+
}
33+
34+
@Test
35+
publicvoidtest2(){
36+
nums =newint[]{23,2,6,4,7};
37+
expected =true;
38+
k =6;
39+
actual =test.checkSubarraySum(nums,k);
40+
assertEquals(expected,actual);
41+
}
42+
43+
@Test
44+
publicvoidtest3(){
45+
nums =newint[]{23,2,6,4,7};
46+
expected =false;
47+
k =0;
48+
actual =test.checkSubarraySum(nums,k);
49+
assertEquals(expected,actual);
50+
}
51+
52+
@Test
53+
publicvoidtest4(){
54+
nums =newint[]{0,1,0};
55+
expected =false;
56+
k =0;
57+
actual =test.checkSubarraySum(nums,k);
58+
assertEquals(expected,actual);
59+
}
60+
61+
@Test
62+
publicvoidtest5(){
63+
nums =newint[]{0,0};
64+
expected =true;
65+
k =0;
66+
actual =test.checkSubarraySum(nums,k);
67+
assertEquals(expected,actual);
68+
}
69+
70+
}

0 commit comments

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