LeetCode1013：将数组分成和相等的三个部分

前言

本系列文章为《leetcode》刷题笔记。

题目位置：力扣中国

项目位置：我的Github项目

题目

给你一个整数数组 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：

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

示例 2：

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

示例 3：

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

提示：

3 <= A.length <= 50000
-10^4 <= A[i] <= 10^4

思路

题目要点：

1. 原数组砍成三段，每段是连续的
2. 每段的和相等
3. 总和/3就是每段的和

方法一：暴力破解

最直观的想法就暴力破解，要把一个线段砍成三段，那必然有两条分隔线，所以有两个循环来改变分隔线的位置。

第一个分隔线由i表示，切分开第一段和第二段，从0开始，最多到len(A)-2，因为后面两段至少要有一个值。区间为[0,i]

第二个分隔线由j表示，切开第二段和第三段，从1开始，给第一段至少一个值，给第最后一段，至少一个值。区间为[i+1,j]，最后一个区间为[j+1,len(A)-1]

 for i := 0; i < len(A)-2; i++ {
        ....
        for j := i + 1; j < len(A)-1; j++ {

这样三段的和为suma,sumb,sumc ，起始值为0。

为了减少循环次数，不要每次改变长度都重新加一次sumc，只要先统计一次第三段的和赋值给tmpsumc留给后面用，每次增加第一段长度就给第二段长度清零，第三段总和等于 tmpsumc

每次前两段长度增加的时候，sumc剪去j新包含的数即可，如下第二层循环：

for j := i + 1; j < len(A)-1; j++ {
            sumb = sumb + A[j]
            sumc = sumc - A[j]
      ......

每次第二段长度增加1、第三段长度减少1，都要进行一次判断是否三个和相等。

如果第二段和第三段各自的和都和第一段不相等，那就先将第三段总和tmpsumc - A[i+1]，让第一段长度加1，第二段长度清零

但是速度很慢：

方法二 ：数学

这真的是一个数学题，如果已知总和，由于三段长度相等，只要找到前两段，那第三段一定相等。

所以有如下代码统计总和

for i := 0; i < len(A); i++ {
    sum = sum + A[i]
  }

如果被3除不尽则失败

sum%3 != 0

找出前两段，count是统计次数

for i := 0; i < len(A); i++ {
    tmpSum = tmpSum + A[i]
    if tmpSum == singeSum {
      count = count + 1
      tmpSum = 0
      if count == 2 && i < len(A)-1 {
        return true
      }
    }
  }

其中count == 2 && i < len(A)-1是保证第三段至少有一个数

ps: 有人会问了，因为数组有正有负，如果我找到了更长的第一段怎么办？

第二段的位置总是在第一段后面的，第一段再长，都是小于第二段的长度的，总和我们都求出来了，只要找到第一段就好啦。

但如果你选择了更大的下标（不妨叫做 i1），可能就没有对应的满足要求的 j 了，所以选最小的是最安全的。只要第一段找到了，后面两段的和必然是sum/3 * 2,找得到就是，找不到就没了。

代码

方法一：暴力破解

Go

func canThreePartsEqualSum(A []int) bool {
  suma, sumb, sumc := 0, 0, 0
  tmpsumc := 0
  for k := 1; k < len(A); k++ {
    tmpsumc = tmpsumc + A[k]
  }
  for i := 0; i < len(A)-2; i++ {
    suma = suma + A[i]
    sumb = 0
    sumc = tmpsumc
    for j := i + 1; j < len(A)-1; j++ {
      sumb = sumb + A[j]
      sumc = sumc - A[j]
      if suma == sumb && sumb == sumc {
        return true
      }
    }
    tmpsumc = tmpsumc - A[i+1]
  }
  return false
}

方法二 ：数学

Go

func canThreePartsEqualSum(A []int) bool {
  tmpSum, sum, singeSum, count := 0, 0, 0, 0
  for i := 0; i < len(A); i++ {
    sum = sum + A[i]
  }
  if sum%3 != 0 {
    return false
  }
  singeSum = sum / 3
  for i := 0; i < len(A); i++ {
    tmpSum = tmpSum + A[i]
    if tmpSum == singeSum {
      count = count + 1
      tmpSum = 0
      if count == 2 && i < len(A)-1 {
        return true
      }
    }
  }
  return false
}