10000 add 1013 · devdcores/Leetcode@cf752f5 · GitHub
[go: up one dir, main page]
Skip to content

Commit cf752f5

Browse files
fishercoder1534fishercoder1534
committed
add 1013
1 parent 42d1ba6 commit cf752f5

File tree

3 files changed

+96
-0
lines changed

3 files changed

+96
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,7 @@ Your ideas/fixes/algorithms are more than welcome!
4242
|1020|[Number of Enclaves](https://leetcode.com/problems/number-of-enclaves/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1020.java) | O(mn) | O(mn) | |Medium|Graph, DFS, BFS, recursion|
4343
|1018|[Binary Prefix Divisible By 5](https://leetcode.com/problems/binary-prefix-divisible-by-5/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1018.java) | O(n) | O(1) | |Easy|
4444
|1014|[Best Sightseeing Pair](https://leetcode.com/problems/best-sightseeing-pair/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1014.java) | O(n) | O(1) | |Medium|
45+
|1013|[Partition Array Into Three Parts With Equal Sum](https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1013.java) | O(n) | O(1) | |Easy|
4546
|1011|[Capacity To Ship Packages Within D Days](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1011.java) | O(nlogn) | O(1) | |Medium|Binary Search|
4647
|1010|[Pairs of Songs With Total Durations Divisible by 60](https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1010.java) | O(n) | O(1) | |Easy|
4748
|1009|[Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1009.java) | O(n) | O(1) | |Easy|

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

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package com.fishercoder.solutions;
2+
3+
/**
4+
* 1013. Partition Array Into Three Parts With Equal Sum
5+
*
6+
* Given an array A of integers, return true if and only if we can partition the array into three non-empty parts with equal sums.
7+
* Formally, we can partition the array if we can find indexes i+1 < j with
8+
* (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1])
9+
*
10+
* Example 1:
11+
* Input: [0,2,1,-6,6,-7,9,1,2,0,1]
12+
* Output: true
13+
* Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
14+
*
15+
* Example 2:
16+
* Input: [0,2,1,-6,6,7,9,-1,2,0,1]
17+
* Output: false
18+
*
19+
* Example 3:
20+
* Input: [3,3,6,5,-2,2,5,1,-9,4]
21+
* Output: true
22+
* Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
23+
*
24+
* Note:
25+
*
26+
* 3 <= A.length <= 50000
27+
* -10000 <= A[i] <= 10000*/
28+
public class _1013 {
29+
public static class Solution1 {
30+
public boolean canThreePartsEqualSum(int[] A) {
31+
int sum = 0;
32+
for (int i = 0; i < A.length; i++) {
33+
sum += A[i];
34+
}
35+
if (sum % 3 != 0) {
36+
return false;
37+
}
38+
int equalSum = sum / 3;
39+
int left = 0;
40+
int leftSum = 0;
41+
while (left < A.length - 2 && leftSum != equalSum) {
42+
leftSum += A[left++];
43+
}
44+
if (left > A.length - 2 || leftSum != equalSum) {
45+
return false;
46+
}
47+
48+
int right = A.length - 1;
49+
int rightSum = 0;
50+
while (right > left && rightSum != equalSum) {
51+
rightSum += A[right--];
52+
}
53+
if (right < left || rightSum != equalSum) {
54+
return false;
55+
}
56+
int middleSum = 0;
57+
for (int i = left; i <= right; i++) {
58+
middleSum += A[i];
59+
}
60+
return middleSum == equalSum;
61+
}
62+
}
63+
}

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

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

0 commit comments

Comments
 (0)
0