Skip to content

Latest commit

 

History

History
 
 

1013.Partition Array Into Three Parts With Equal Sum

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
README_EN.md
README_EN.md
 
 
Solution.cpp
Solution.cpp
 
 
Solution.go
Solution.go
 
 
Solution.java
Solution.java
 
 
Solution.py
Solution.py
 
 

README.md

comments difficulty edit_url rating source tags
true
简单
1378
第 129 场周赛 Q1
贪心
数组

1013. 将数组分成和相等的三个部分

English Version

题目描述

给你一个整数数组 arr，只有可以将其划分为三个和相等的 非空 部分时才返回 true，否则返回 false。

形式上，如果可以找出索引 i + 1 < j 且满足 (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1]) 就可以将数组三等分。

 

示例 1：

输入：arr = [0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

示例 2：

输入：arr = [0,2,1,-6,6,7,9,-1,2,0,1]
输出：false

示例 3：

输入：arr = [3,3,6,5,-2,2,5,1,-9,4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

 

提示：

  • 3 <= arr.length <= 5 * 104
  • -104 <= arr[i] <= 104

解法

方法一：双指针

先遍历数组 arr，得到数组所有元素的和，记为 s。如果 s 不能被 3 整除，那么数组 arr 不能被分成和相等的三个部分，直接返回 false。

接下来，利用双指针 i, j 找三等分和的边界，若成功找到，返回 true，否则返回 false。

时间复杂度 $O(n)$，空间复杂度 $O(1)$，其中 $n$ 为数组 arr 的长度。

Python3

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

Java

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;
    }
}

C++

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& arr) {
        int s = 0;
        for (int v : arr) s += v;
        if (s % 3) return false;
        int i = 0, j = arr.size() - 1;
        int a = 0, b = 0;
        while (i < arr.size()) {
            a += arr[i];
            if (a == s / 3) {
                break;
            }
            ++i;
        }
        while (~j) {
            b += arr[j];
            if (b == s / 3) {
                break;
            }
            --j;
        }
        return i < j - 1;
    }
};

Go

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
}