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

发表于 | 分类于
字数统计: 379 | 阅读时长 ≈ 1

一、题目描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  1. 3 <= A.length <= 50000
  2. -10000 <= A[i] <= 10000

二、题解

1.算法描述

  • 双指针

2.个人分析

  • 双指针向数组中间遍历，如果头尾指针遍历的累加都等于整个数组和的1/3，则判断头尾指针之间元素的累加是否等于数组的1/3即可

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int summ(int *A, int a, int b)
{
    int sum = 0;
    for (; a <= b; a++)
        sum += A[a];
    return sum;
}
bool canThreePartsEqualSum(int *A, int ASize)
{
    int i;
    int sum = 0;
    for (i = 0; i < ASize; i++)
        sum += A[i];
    if (sum % 3 != 0)
        return false;
    int oneThird = sum / 3;
    int m = 0, n = ASize - 1;
    int qian = 0, hou = 0;
    while (m <= n)
    {
        if (qian != oneThird)
        {
            qian += A[m];
            m++;
        }
        else if (hou != oneThird)
        {
            hou += A[n];
            n--;
        }
        else if (summ(A, m, n) == oneThird)
            return true;
    }
    return false;
}