[LeetCode] 1013、将数组分成和相等的三个部分

题目描述

给你一个整数数组

A

，只有可以将其划分为三个和相等的非空部分时才返回

true

，否则返回

false

。

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

解题思路

此题最简单的思路就是从头直接开始找，比较暴力，但是时间复杂度也是 O ( n ) O(n) O(n)。用双指针的思路理论上会更快一点。

• 双指针法：
  • 数组元素的总和

    sum

    不是

    3

    的倍数，直接返回

    false

    。
  • 使用双指针

    left

    ，

    right

    从数组两头开始一起找，节约时间。
  • 在

    left + 1 < right

    的约束下，如果可以满足数组两头的和都是

    sum/3

    ，那么中间剩下的元素和也一定是

    sum/3

    。（使用

    left + 1 < right

    的约束就是要中间有剩下的元素，如果使用

    left < right

    的约束，那么数组可能恰好被划分成两部分，中间没有元素）

参考代码

双指针法

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % 3 != 0)
            return false;
        
        int length = nums.size();
        int left = 0, leftSum = nums[0];
        int right = length - 1, rightSum = nums[length - 1];
        // 使用left + 1 < right 的原因，防止只能将数组分成两个部分
        // 例如：[1,-1,1,-1]，使用left < right作为判断条件就会出错
        while(left + 1 < right){
            if(leftSum == sum/3 && rightSum == sum/3)
                return true;
            
            if(leftSum != sum/3)
                leftSum += nums[++left];
            if(rightSum != sum/3)
                rightSum += nums[--right];
        }
        
        return false;
    }
};
           

暴力法（很巧妙）

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % 3 != 0)
            return false;
        
        int curSum = 0, cnt = 0;
        for(auto num: nums){
            curSum += num;
            if(curSum == sum/3){
                cnt++;
                curSum = 0;
            }
        }
        
        // cnt不一定等于3，例如[1,-1,1,-1,1,-1,1,-1]
        return cnt >= 3;
    }
};