8000 add 560 · bloomer1/Leetcode@b215682 · GitHub
[go: up one dir, main page]
Skip to content

Commit b215682

Browse files
fishercoder1534fishercoder1534
committed
add 560
1 parent 9ebe7b8 commit b215682

File tree

4 files changed

+69
-1
lines changed

4 files changed

+69
-1
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@ Your ideas/fixes/algorithms are more than welcome!
2525
|563|[Binary Tree Tilt](https://leetcode.com/problems/binary-tree-tilt/)|[Solution](../master/src/main/java/com/stevesun/solutions/_563.java) | O(n) |O(n) | Easy | Tree Recursion
2626
|562|[Longest Line of Consecutive One in Matrix](https://leetcode.com/problems/longest-line-of-consecutive-one-in-matrix/)|[Solution](../master/src/main/java/com/stevesun/solutions/_562.java) | O(m*n) |O(m*n) | Medium | Matrix DP
2727
|561|[Array Partition I](https://leetcode.com/problems/array-partition-i/)|[Solution](../master/src/main/java/com/stevesun/solutions/_561.java) | O(nlogn) |O(1) | Easy | Array
28+
|560|[Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/)|[Solution](../master/src/main/java/com/stevesun/solutions/_560.java) | O(n) |O(n) | Medium | Array, HashMap
2829
|557|[Reverse Words in a String III](https://leetcode.com/problems/reverse-words-in-a-string-iii/)|[Solution](../master/src/main/java/com/stevesun/solutions/ReverseWordsinaStringIII.java) | O(n) |O(n) | Easy | String
2930
|556|[Next Greater Element III](https://leetcode.com/problems/next-greater-element-iii/)|[Solution](../master/src/main/java/com/stevesun/solutions/NextGreaterElementIII.java) | O(n)|O(1)| Medium | String
3031
|555|[Split Concatenated Strings](https://leetcode.com/problems/split-concatenated-strings/)|[Solution](../master/src/main/java/com/stevesun/solutions/_555.java) | O(n^2) |O(n) | Medium | String

‎src/main/java/com/stevesun/solutions/PalindromePermutationII.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,7 @@
1717
Hint:
1818
1919
If a palindromic permutation exists, we just need to generate the first half of the string.
20-
To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.
20+
To generate all distinct permutations of a (half of) string, use a similar approach from: _46 II or Next Permutation.
2121
*/
2222
public class PalindromePermutationII {
2323

‎src/main/java/com/stevesun/solutions/_560.java

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package com.stevesun.solutions;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* 560. Subarray Sum Equals K
8+
*
9+
* Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
10+
11+
Example 1:
12+
Input:nums = [1,1,1], k = 2
13+
Output: 2
14+
Note:
15+
The length of the array is in range [1, 20,000].
16+
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
17+
*/
18+
public class _560 {
19+
20+
public int subarraySum(int[] nums, int k) {
21+
Map<Integer, Integer> preSum = new HashMap();
22+
int sum = 0;
23+
int result = 0;
24+
preSum.put(0, 1);
25+
for (int i = 0; i < nums.length; i++) {
26+
sum += nums[i];
27+
if (preSum.containsKey(sum - k)) {
28+
result += preSum.get(sum-k);
29+
}
30+
preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
31+
}
32+
return result;
33+
}
34+
35+
}

‎src/test/java/com/stevesun/_560Test.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.stevesun;
2+
3+
import com.stevesun.solutions._560;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertEquals;
8+
9+
/**
10+
* Created by stevesun on 4/29/17.
11+
*/
12+
public class _560Test {
13+
private static _560 test;
14+
private static int expected;
15+
private static int actual;
16+
private static int[] nums;
17+
private static int k;
18+
19+
@BeforeClass
20+
public static void setup(){
21+
test = new _560();
22+
}
23+
24+
@Test
25+
public void test1(){
26+
nums = new int[]{1,1,1};
27+
k = 2;
28+
expected = 2;
29+
actual = test.subarraySum(nums, k);
30+
assertEquals(expected, actual);
31+
}
32+
}

0 commit comments

Comments
 (0)
0