1013. 将数组分成和相等的三个部分 - 力扣（LeetCode）

发布：2021年10月7日21:18:48

问题描述及示例

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的题解（Array.reduce()；双指针）

如果 arr 能够被三等分，那么 arr 数组元素的总和（即下面的 sum 变量存储的值）一定是 3 的倍数，且每一部分的总和（即下面的 target 变量存储的值）为 sum / 3。

用指针 i 和指针 j 将 arr 数组分割为三个部分，同时创建一个长度为 3 的数组 parts 用来存储每一部分的总和。

总体分为四大步：

先利用 reduce() 函数计算 arr 数组的总和 sum。（当然其他计算总和的方法也可以）
先让 i 指针指向 arr 数组头部，然后让其逐位往后移动，并将每一位遍历的结果累加到 parts[0] 身上。直到 parts[0] 累加至 target 或者 i 指针到达数组尾部。（即第一个 while 循环）
再让 j 指针指向 arr 数组尾部，然后让其逐位往前移动，并将每一位遍历的结果累加到 parts[2] 身上。直到 parts[2] 累加至 target 或者 j 比 i 小。（即第二个 while 循环）
经过上面的【2】和【3】，指针 i 和指针 j 就可以确定一个范围，而该范围就是第二部分。最后再利用 reduce() 函数计算第二部分的元素总和。（当然其他计算总和的方法也可以）

其中最关键的就是第二步和第三步，需要考虑各种有效情况和无效情况，我就是在这里连续遭受了两次毒打：

在这里插入图片描述

第一次毒打：没有考虑第一位数就大于 target 的情况

在这里插入图片描述

第二次毒打：没有考虑 target 为 0 的情况

经过这两次毒打，终于算是通过了提交。相关详解请看下方注释：

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var canThreePartsEqualSum = function(arr) {
  // 先利用 `reduce()` 函数计算 `arr` 数组的总和 `sum`
  let sum = arr.reduce((acc, cur) => acc + cur);
  // 如果 sum 不是 3 的倍数，则 arr 一定不能三等分，所以可以直接返回 false
  if(sum % 3) {
    return false;
  }
  // target是每一部分的目标总和
  let target = sum / 3;
  // i和j指针用于将arr分割为三部分
  let i = 0;
  let j = arr.length - 1;
  // parts是一个长度为3的数组，用于存储遍历过程中所存储的三个部分的总和
  let parts = new Array(3);
  // 开始确定第一部分的右边界
  while(parts[0] !== target && i < arr.length) {
    parts[0] = parts[0] === undefined ? 0 : parts[0];
    parts[0] += arr[i];
    i++;
  }
  // 如果上面的while循环结束了，说明parts[0]已经累加到了target，或者是i已经到了数组末尾
  // 如果是第二种情况，则说明arr不能三等分，所以应该直接返回false
  if(i === arr.length-1) {
    return false;
  }
  // 开始确定第三部分的左边界
  while(parts[2] !== target && j >= i) {
    parts[2] = parts[2] === undefined ? 0 : parts[2];
    parts[2] += arr[j];
    j--;
  }
  // 如果上面的while循环结束了，说明parts[2]已经累加到了target，或者是j已经到了i前面
  // 如果是第二种情况，则说明arr不能三等分，所以应该直接返回false
  if(j < i){
    return false;
  }
  // 再次利用reduce函数计算i和j之间的元素总和，即第二部分的总和
  parts[1] = arr.slice(i, j+1).reduce((acc, cur) => acc + cur);
  // 如果第二个部分的总和不为target，则说明arr不能三等分，所以应该直接返回false
  if(parts[1] !== target){
    return false;
  }
  // 最后，如果之前所有的检验都通过了，则说明arr可以被三等分，所以返回true
  return true;
};


提交记录
72 / 72 个通过测试用例
状态：通过
执行用时：100 ms, 在所有 JavaScript 提交中击败了19.47%的用户
内存消耗：44 MB, 在所有 JavaScript 提交中击败了7.46%的用户
时间：2021/10/07 21:23