8000 refactor 548 · codingwhite/Leetcode-4@e9bf839 · GitHub
[go: up one dir, main page]
Skip to content

Commit e9bf839

Browse files
fishercoder1534fishercoder1534
committed
refactor 548
1 parent 90e16ea commit e9bf839

File tree

3 files changed

+20
-50
lines changed

3 files changed

+20
-50
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -109,7 +109,7 @@ Your ideas/fixes/algorithms are more than welcome!
109109
|552|[Student Attendance Record II](https://leetcode.com/problems/student-attendance-record-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_552.java) | O(n)| O(1) | Hard| DP
110110
|551|[Student Attendance Record I](https://leetcode.com/problems/student-attendance-record-i/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_551.java) | O(n)| O(1) | Easy| String
111111
|549|[Binary Tree Longest Consecutive Sequence II](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_549.java) | O(n) |O(n) | Medium | Tree
112-
|548|[Split Array with Equal Sum](https://leetcode.com/problems/split-array-with-equal-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_548.java) | O(n^2) |O(1) | Medium | Array
112+
|548|[Split Array with Equal Sum](https://leetcode.com/problems/split-array-with-equal-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_548.java) | O(n^2) |O(n) | Medium | Array
113113
|547|[Friend Circles](https://leetcode.com/problems/friend-circles/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_547.java) | O(n^2) |O(n) | Medium | Union Find
114114
|546|[Remove Boxes](https://leetcode.com/problems/remove-boxes/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_546.java) | O(n^3) |O(n^3) | Hard| DFS, DP
115115
|545|[Boundary of Binary Tree](https://leetcode.com/problems/boundary-of-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_545.java) | O(n) |O(n) | Medium | Recursion

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

Lines changed: 15 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,15 @@
11
package com.fishercoder.solutions;
22

33
import java.util.HashSet;
4+
import java.util.Set;
45

56
/**
7+
* 548. Split Array with Equal Sum
8+
*
69
* Given an array with n integers, you need to find if there are triplets (i, j, k) which satisfies following conditions:
7-
8-
0 < i, i + 1 < j, j + 1 < k < n - 1
9-
Sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) should be equal.
10-
where we define that subarray (L, R) represents a slice of the original array starting from the element indexed L to the element indexed R.
10+
* 0 < i, i + 1 < j, j + 1 < k < n - 1
11+
* Sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) should be equal.
12+
* where we define that subarray (L, R) represents a slice of the original array starting from the element indexed L to the element indexed R.
1113
1214
Example:
1315
Input: [1,2,1,2,1,2,1]
@@ -25,57 +27,25 @@ where we define that subarray (L, R) represents a slice of the original array st
2527
*/
2628
public class _548 {
2729

28-
public boolean splitArray_O_N_3(int[] nums) {
29-
//TODO: this one is failed by test4, probably some index wrong
30-
if (nums == null || nums.length == 0) {
31-
return false;
32-
}
33-
long[] previousSums = new long[nums.length + 1];
34-
for (int i = 1; i <= nums.length; i++) {
35-
previousSums[i] = previousSums[i - 1] + nums[i - 1];
36-
}
37-
38-
int n = nums.length;
39-
for (int i = 1; i <= n - 6; i++) {
40-
long sum1 = previousSums[i] - previousSums[0];
41-
for (int j = i + 2; j <= n - 4; j++) {
42-
long sum2 = previousSums[j] - previousSums[i + 1];
43-
if (sum1 != sum2) {
44-
break;
45-
}
46-
for (int k = j + 2; k <= n - 2; k++) {
47-
long sum3 = previousSums[k] - previousSums[j + 1];
48-
if (sum2 != sum3) {
49-
break;
50-
}
51-
long sum4 = previousSums[n] - previousSums[k + 1];
52-
if (sum3 == sum4) {
53-
return true;
54-
}
55-
}
56-
}
57-
}
58-
return false;
59-
}
60-
61-
public boolean splitArray_O_N_2(int[] nums) {
62-
if (nums.length < 7) {
30+
public boolean splitArray(int[] nums) {
31+
int len = nums.length;
32+
if (len < 7) {
6333
return false;
6434
}
65-
int[] sum = new int[nums.length];
35+
int[] sum = new int[len];
6636
sum[0] = nums[0];
67-
for (int i = 1; i < nums.length; i++) {
37+
for (int i = 1; i < len; i++) {
6838
sum[i] = sum[i - 1] + nums[i];
6939
}
70-
for (int j = 3; j < nums.length - 3; j++) {
71-
HashSet<Integer> set = new HashSet<>();
40+
for (int j = 3; j < len - 3; j++) {
41+
Set<Integer> set = new HashSet<>();
7242
for (int i = 1; i < j - 1; i++) {
7343
if (sum[i - 1] == sum[j - 1] - sum[i]) {
7444
set.add(sum[i - 1]);
7545
}
7646
}
77-
for (int k = j + 2; k < nums.length - 1; k++) {
78-
if (sum[nums.length - 1] - sum[k] == sum[k - 1] - sum[j] && set.contains(sum[k - 1] - sum[j])) {
47+
for (int k = j + 2; k < len - 1; k++) {
48+
if (sum[len - 1] - sum[k] == sum[k - 1] - sum[j] && set.contains(sum[k - 1] - sum[j])) {
7949
return true;
8050
}
8151
}

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

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -27,15 +27,15 @@ public void setupForEachTest() {
2727
public void test1() {
2828
nums = new int[]{1, 2, 1, 2, 1, 2, 1};
2929
expected = true;
30-
actual = test.splitArray_O_N_3(nums);
30+
actual = test.splitArray(nums);
3131
assertEquals(expected, actual);
3232
}
3333

3434
@Test
3535
public void test2() {
3636
nums = new int[]{1, 2, 1, 2, 1, 2, 1, 2};
3737
expected = false;
38-
actual = test.splitArray_O_N_3(nums);
38+
actual = test.splitArray(nums);
3939
assertEquals(expected, actual);
4040
}
4141

@@ -2045,7 +2045,7 @@ public void test3() {
20452045
};
20462046
expected = false;
20472047
long start = System.currentTimeMillis();
2048-
actual = test.splitArray_O_N_3(nums);
2048+
actual = test.splitArray(nums);
20492049
System.out.println("It took " + (System.currentTimeMillis() - start) + " ms to solve this test case.");
20502050
assertEquals(expected, actual);
20512051
}
@@ -2055,7 +2055,7 @@ public void test4() {
20552055
//equalSum is 3, j = 6, k = 9
20562056
nums = new int[]{1, 2, 1, 3, 0, 0, 2, 2, 1, 3, 3};
20572057
expected = true;
2058-
actual = test.splitArray_O_N_2(nums);
2058+
actual = test.splitArray(nums);
20592059
assertEquals(expected, actual);
20602060
}
20612061
}

0 commit comments

Comments
 (0)
0