Skip to content

Commit 3014298

Browse files
fishercoder1534fishercoder1534
committed
[N-0] refactor 325
1 parent 24b385a commit 3014298

File tree

3 files changed

+64
-62
lines changed

3 files changed

+64
-62
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -357,7 +357,7 @@ Your ideas/fixes/algorithms are more than welcome!
357357
|328|[Odd Even Linked List](https://leetcode.com/problems/odd-even-linked-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_328.java)| O(n)|O(1) | Medium| Linked List
358358
|327|[Count of Range Sum](https://leetcode.com/problems/count-of-range-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_327.java)| O(?)|O(?) | Hard|
359359
|326|[Power of Three](https://leetcode.com/problems/power-of-three/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_326.java)| O(1)|O(1) | Easy| Math
360-
|325|[Maximum Size Subarray Sum Equals k](https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_325.java)| O(n)|O(n) | Medium| Sort
360+
|325|[Maximum Size Subarray Sum Equals k](https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_325.java)| O(n)|O(n) | Medium| HashTable
361361
|324|[Wiggle Sort II](https://leetcode.com/problems/wiggle-sort-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_324.java)| O(n)|O(n) | Medium| Sort
362362
|323|[Number of Connected Components in an Undirected Graph](https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_323.java)| O(?)|O(?)| Medium|
363363
|322|[Coin Change](https://leetcode.com/problems/coin-change/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_322.java)| O(n*k)|O(k) | Medium| DP

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

Lines changed: 34 additions & 61 deletions
Original file line numberDiff line numberDiff line change
@@ -1,74 +1,47 @@
11
package com.fishercoder.solutions;
22

3-
import com.fishercoder.common.utils.CommonUtils;
4-
53
import java.util.HashMap;
64
import java.util.Map;
75

8-
/**Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.
9-
10-
Note:
11-
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.
12-
13-
Example 1:
14-
Given nums = [1, -1, 5, -2, 3], k = 3,
15-
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)
16-
17-
Example 2:
18-
Given nums = [-2, -1, 2, 1], k = 1,
19-
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)
20-
21-
Follow Up:
22-
Can you do it in O(n) time?*/
6+
/**
7+
* 325. Maximum Size Subarray Sum Equals k
8+
*
9+
* Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.
10+
*
11+
* Note:
12+
* The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.
13+
*
14+
* Example 1:
15+
* Given nums = [1, -1, 5, -2, 3], k = 3,
16+
* return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)
17+
*
18+
* Example 2:
19+
* Given nums = [-2, -1, 2, 1], k = 1,
20+
* return 2. (because the subarray [-1, 2] sums to 1 and is the longest)
21+
*
22+
* Follow Up:
23+
* Can you do it in O(n) time?*/
2324

2425
public class _325 {
25-
public int maxSubArrayLen_On_solution(int[] nums, int k) {
26-
Map<Integer, Integer> map = new HashMap();
27-
int sum = 0;
28-
int max = 0;
29-
for (int i = 0; i < nums.length; i++) {
30-
sum += nums[i];
31-
if (sum == k) {
32-
max = i + 1;
33-
} else if (map.containsKey(sum - k)) {
34-
max = Math.max(max, i - map.get(sum - k));
35-
}
36-
if (!map.containsKey(sum)) {
37-
map.put(sum, i);
38-
}
39-
}
40-
return max;
41-
}
42-
4326

44-
public static int maxSubArrayLen_On2_solution(int[] nums, int k) {
45-
//NOTES: didn't finish this one
46-
int[] sums = new int[nums.length];
47-
int max = 0;
48-
for (int i = 0; i < nums.length; i++) {
49-
if (i == 0) {
50-
sums[i] = nums[i];
51-
} else {
52-
sums[i] = sums[i - 1] + nums[i];
53-
}
54-
if (sums[i] == k) {
55-
max = i + 1;//then this one must be the max
27+
public static class Solution1 {
28+
public int maxSubArrayLen(int[] nums, int k) {
29+
Map<Integer, Integer> map = new HashMap();
30+
int sum = 0;
31+
int max = 0;
32+
for (int i = 0; i < nums.length; i++) {
33+
sum += nums[i];
34+
if (sum == k) {
35+
max = i + 1;
36+
} else if (map.containsKey(sum - k)) {
37+
max = Math.max(max, i - map.get(sum - k));
38+
}
39+
if (!map.containsKey(sum)) {
40+
map.put(sum, i);
41+
}
5642
}
43+
return max;
5744
}
58-
CommonUtils.printArray(sums);
59-
//do computation for each possible subarray of sums and find the max length
60-
return max;
6145
}
6246

63-
public static void main(String... args) {
64-
//correct answer is 4
65-
// int[] nums = new int[]{1, -1, 5, -2, 3};
66-
// int k = 3;
67-
68-
//correct answer is 2
69-
int[] nums = new int[]{-2, -1, 2, 1};
70-
int k = 1;
71-
maxSubArrayLen_On2_solution(nums, k);
72-
}
73-
7447
}

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

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._325;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertEquals;
8+
9+
public class _325Test {
10+
private static _325.Solution1 solution1;
11+
private static int[] nums;
12+
13+
@BeforeClass
14+
public static void setup() {
15+
solution1 = new _325.Solution1();
16+
}
17+
18+
@Test
19+
public void test1() {
20+
nums = new int[]{-2, -1, 2, 1};
21+
assertEquals(2, solution1.maxSubArrayLen(nums, 1));
22+
}
23+
24+
@Test
25+
public void test2() {
26+
nums = new int[]{1, -1, 5, -2, 3};
27+
assertEquals(4, solution1.maxSubArrayLen(nums, 3));
28+
}
29+
}

0 commit comments

Comments
 (0)