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

Commite9bf839

Browse files
refactor 548
1 parent90e16ea commite9bf839

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
packagecom.fishercoder.solutions;
22

33
importjava.util.HashSet;
4+
importjava.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
publicclass_548 {
2729

28-
publicbooleansplitArray_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-
returnfalse;
32-
}
33-
long[]previousSums =newlong[nums.length +1];
34-
for (inti =1;i <=nums.length;i++) {
35-
previousSums[i] =previousSums[i -1] +nums[i -1];
36-
}
37-
38-
intn =nums.length;
39-
for (inti =1;i <=n -6;i++) {
40-
longsum1 =previousSums[i] -previousSums[0];
41-
for (intj =i +2;j <=n -4;j++) {
42-
longsum2 =previousSums[j] -previousSums[i +1];
43-
if (sum1 !=sum2) {
44-
break;
45-
}
46-
for (intk =j +2;k <=n -2;k++) {
47-
longsum3 =previousSums[k] -previousSums[j +1];
48-
if (sum2 !=sum3) {
49-
break;
50-
}
51-
longsum4 =previousSums[n] -previousSums[k +1];
52-
if (sum3 ==sum4) {
53-
returntrue;
54-
}
55-
}
56-
}
57-
}
58-
returnfalse;
59-
}
60-
61-
publicbooleansplitArray_O_N_2(int[]nums) {
62-
if (nums.length <7) {
30+
publicbooleansplitArray(int[]nums) {
31+
intlen =nums.length;
32+
if (len <7) {
6333
returnfalse;
6434
}
65-
int[]sum =newint[nums.length];
35+
int[]sum =newint[len];
6636
sum[0] =nums[0];
67-
for (inti =1;i <nums.length;i++) {
37+
for (inti =1;i <len;i++) {
6838
sum[i] =sum[i -1] +nums[i];
6939
}
70-
for (intj =3;j <nums.length -3;j++) {
71-
HashSet<Integer>set =newHashSet<>();
40+
for (intj =3;j <len -3;j++) {
41+
Set<Integer>set =newHashSet<>();
7242
for (inti =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 (intk =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 (intk =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
returntrue;
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
publicvoidtest1() {
2828
nums =newint[]{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
publicvoidtest2() {
3636
nums =newint[]{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
longstart =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 =newint[]{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)
[8]ページ先頭
©2009-2025 Movatter.jp