【算法-LeetCode】1013. 将数组分成和相等的三个部分(Array.reduce();双指针)

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 和 指针 jarr 数组分割为三个部分,同时创建一个长度为 3 的数组 parts 用来存储每一部分的总和。

总体分为四大步:

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

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

【算法-LeetCode】1013. 将数组分成和相等的三个部分(Array.reduce();双指针)

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

【算法-LeetCode】1013. 将数组分成和相等的三个部分(Array.reduce();双指针)

第二次毒打:没有考虑 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

可以看到上面的这种解法的时间和空间表现都不大好。有一些逻辑其实重复了,可以做一些抽取来让代码看起来更精简。

上面用到了数组对象的 reduce() 方法:

【算法-LeetCode】1013. 将数组分成和相等的三个部分(Array.reduce();双指针)

利用 reduce() 方法进行数组求和

具体可以参考下方MDN文档:

参考:Array.prototype.reduce() - JavaScript | MDN

官方题解

更新:2021年7月29日18:43:21

因为我考虑到著作权归属问题,所以【官方题解】部分我不再粘贴具体的代码了,可到下方的链接中查看。

更新:2021年10月7日22:53:39

参考:将数组分成和相等的三个部分 - 将数组分成和相等的三个部分 - 力扣(LeetCode)

【更新结束】

有关参考

更新:2021年10月7日21:19:57
参考:Array.prototype.reduce() - JavaScript | MDN

上一篇:【OpenCV】cv2.putText()函数用法


下一篇:AttributeError: module ‘cv2‘ has no attribute ‘imread‘问题的解决方法