Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1013.html
1013. Partition Array Into Three Parts With Equal Sum (Easy)
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.
Formally, we can partition the array if we can find indexes i+1 < j
with (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1])
Example 1:
Input: A = [0,2,1,-6,6,-7,9,1,2,0,1] Output: true Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
Example 2:
Input: A = [0,2,1,-6,6,7,9,-1,2,0,1] Output: false
Example 3:
Input: A = [3,3,6,5,-2,2,5,1,-9,4] Output: true Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
Constraints:
3 <= A.length <= 50000
-10^4 <= A[i] <= 10^4
Related Topics:
Array
Solution 1.
-
class Solution { public boolean canThreePartsEqualSum(int[] A) { int sum = 0; for (int num : A) sum += num; if (sum % 3 != 0) return false; int partSum = sum / 3; int count = 0; int curSum = 0; int length = A.length; for (int i = 0; i < length; i++) { curSum += A[i]; if (curSum == partSum * (count + 1)) count++; } return count >= 3; } } ############ class Solution { public boolean canThreePartsEqualSum(int[] arr) { int s = 0; for (int v : arr) { s += v; } if (s % 3 != 0) { return false; } int i = 0, j = arr.length - 1; int a = 0, b = 0; while (i < arr.length) { a += arr[i]; if (a == s / 3) { break; } ++i; } while (j >= 0) { b += arr[j]; if (b == s / 3) { break; } --j; } return i < j - 1; } }
-
// OJ: https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/ // Time: O(N) // Space: O(1) class Solution { public: bool canThreePartsEqualSum(vector<int>& A) { int total = accumulate(begin(A), end(A), 0), cnt = 0, sum = 0; if (total % 3) return false; total /= 3; for (int i = 0; i < A.size() - 1; ++i) { sum += A[i]; if (sum == total) { sum = 0; ++cnt; } if (cnt == 2) return true; } return false; } };
-
class Solution: def canThreePartsEqualSum(self, arr: List[int]) -> bool: s = sum(arr) if s % 3 != 0: return False i, j = 0, len(arr) - 1 a = b = 0 while i < len(arr): a += arr[i] if a == s // 3: break i += 1 while ~j: b += arr[j] if b == s // 3: break j -= 1 return i < j - 1 ############ class Solution(object): def numPairsDivisibleBy60(self, time): """ :type time: List[int] :rtype: int """ count = collections.Counter(time) key = list(count.keys()) N = len(key) res = 0 for i, t in enumerate(key): for j in range(i, N): if (t + key[j]) % 60 == 0: if i == j: res += count[t] * (count[t] - 1) / 2 else: res += count[t] * count[key[j]] return res
-
func canThreePartsEqualSum(arr []int) bool { s := 0 for _, v := range arr { s += v } if s%3 != 0 { return false } i, j := 0, len(arr)-1 a, b := 0, 0 for i < len(arr) { a += arr[i] if a == s/3 { break } i++ } for j >= 0 { b += arr[j] if b == s/3 { break } j-- } return i < j-1 }