删除两个元素以在O（n）中将数组平均分为三部分 [英] Drop two elements to split the array to three part evenly in O(n)

问题描述

我遇到一个让您在数组中放置两个元素以使三部分之和相等的问题。

I encounter a problem to let you drop two elements in an array to make the three part's sum equal.

  Ex:
  1 2 4 3 5 2 1
  After I drop the 4 and 5, it becomes 1, 2 | 3 | 2, 1

约束：

  1.Numbers are all integer > 0

  2.Drop two elements in the array, so the three splitted subarrays will have same subarray sum.

我已经尝试过使用两次通过算法，如下所示

I have tried it by using two pass algorithm as the following

第一遍：O（n）
从左边算出累加总和，这样我就可以轻松获得范围总和。

First pass:O(n) Count the accumulated sum from the left so I can get the range sum easily.

第二遍：O（n ^ 2）
使用嵌套循环获取子数组的开始和结束索引。然后，计算左，中，右总和。

Second pass:O(n^2) Use nested loop to get the subarray's start and end index. Then, calculate the left, mid, right sum.

// 1.get accumulated sum map
int[] sumMap = new int[A.length];
int sum = 0;
for(int i = 0; i < A.length; i ++) {
    sum += A[i];
    sumMap[i] = sum;
}

// 2.try each combination
for(int i = 1; i < A.length - 1; i ++) {
    for(int j = i + 1; j < A.length - 1; j ++) {
        int left = sumMap[i] - A[i];
        int mid = sumMap[j] - sumMap[i] - A[j];
        int right = sumMap[A.length - 1] - sumMap[j];

        if(left == mid && mid == right)return true;
    }
}

有没有更好的算法可以实现O（n ）？

Are there any better algorithm that can achieve O(n)?

谢谢

推荐答案

假定第一个和最后一个元素可以不会被删除，所有元素都是> 0 ：

Assuming that first and last element can't be dropped and all elements are >0:

设置变量 sumleft 表示第一个元素的值， sumright 表示最后一个元素的值。您还需要索引变量来记住左侧和右侧的哪些元素已添加到总和中。

Set a variable sumleft to value of first element, sumright to value of last element. You also need index variables to remember which elements from left and right were already added to the sums.

1. 如果 sumleft == sumright ，测试是否可以删除左侧和右侧的下一个元素以满足要求。如果是这样->完成。如果不是，则从左右取下一个元素，并将其添加到相应的sum变量中。返回1。

1. If sumleft == sumright, test if next elements from left and right can be dropped to fulfill requirement. If so -> done. If not take next elements from left and right and add it to the respective sum variable. Back to 1.

如果 sumleft< sumright ，将左侧的下一个值添加到 sumleft 。返回1。

If sumleft < sumright, add next value from the left to sumleft. Back to 1.

如果所有元素都被消耗，则没有解决方案。

If all elements were consumed, there is no solution.

编辑：测试是否可以通过最初汇总所有元素来完成 sumleft == sumright 是否满足要求（也只需要 O（n ）），然后检查此总和减去要删除的元素是否等于 sumleft * 3 。

Testing if requirement is fulfilled when sumleft == sumright can be done by initially summing up all elements (also needs only O(n)) and checking if this sum minus the elements to drop is equal sumleft * 3.

这篇关于删除两个元素以在O（n）中将数组平均分为三部分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！