在O(n)时间复杂度内将数组分成三个相等的部分，需要删除两个元素。

Question

我遇到了一个问题，让你删除数组中的两个元素，使得三个部分的和相等。

  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.

我已经尝试使用以下的双遍历算法：

第一遍历：O(n) 从左侧开始计算累加和，这样我就可以轻松地获取范围内的和。

第二遍历：O(n^2) 使用嵌套循环来获取子数组的起始和结束索引。然后计算左、中、右的总和。

// 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)？

谢谢

- Jason

---

展示你所尝试过的内容。 - Scary Wombat

问题描述非常模糊。您提供了一个例子，但几乎没有实际提及约束或要求。 - Ali Elgazar

@jason 你有这个问题的最新解决方案吗？ - Danish

Answer 1

• 步骤 1：创建一个求数组

• 步骤 2：采用双指针方法

  public boolean solution(int[] A) {

  int leftPointer = 1;
  int rightPointer = A.length - 2;
  int leftPartSum, middlePartSum, rightPartSum;
  int[] sumArray = new int[A.length];

  // Initializing the sum array
  sumArray[0] = A[0];
  for(int i = 1; i < A.length; i ++)
      sumArray[i] = sumArray[i-1] +  A[i];

  // Using two Pointer technique
  while(leftPointer < rightPointer) {

      leftPartSum = sumArray[leftPointer] - A[leftPointer];
      middlePartSum = sumArray[rightPointer] - sumArray[leftPointer] - A[rightPointer];
      rightPartSum = sumArray[A.length - 1] - sumArray[rightPointer];

      if(leftPartSum == middlePartSum && middlePartSum == rightPartSum)
          return true;

      if (leftPartSum < rightPartSum)
          leftPointer++;
      else if (leftPartSum > rightPartSum)
          rightPointer--;
      else{                   // Else condition denotes: leftPartSum == rightPartSum
          leftPointer++;
          rightPointer--;
      }
  }
  return false; // If no solution is found then returning false
  }

详细说明：

求和数组：在第一次遍历数组时，从左到右计算累加和。尽管这需要O(n)时间创建一个求和数组，但这将帮助您在任何给定时间内以O(1)获得leftPartSum、middlePartSum和rightPartSum。

双指针方法：在双指针方法中，一个指针从开头开始，另一个指针从结尾开始。

在这种情况下，如果我们删除了第一个元素或最后一个元素，则没有办法将数组分成3个相等的部分。因此，我们可以安全地假设

int leftPointer = 1; 
int rightPointer = A.length - 2;

注意: 数组是从0到n-1索引的;

现在，我们将指针相向移动，并且在每次移动时计算左部分和、中间部分和和右部分和。需要移动左指针还是右指针取决于左部分和或右部分和中哪个较小。

- Devender Goyal

---

抱歉，移动指针向左部分和右部分前进的目的是什么？你能解释一下吗？另外为什么我们不能选择第一个和最后一个位置呢？你说没有办法将其分成三个相等的部分，但为什么呢？ - StuartDTO

请让我理解它，你能给我解释一下吗？ - StuartDTO

@StuartDTO 如果你取第一个元素，那么你就没有留下任何元素在它的左边了，因此你最多只能将数组分成两部分...除非你删除最后一个元素，那么你只剩下数组的一部分：中间部分。例如，如果你取数组 [2, 4, 5, 3, 3, 9, 2, 2, 2] 的第二个和第七个元素，那么我们会得到三个部分：[2]、[5, 3, 3, 9] 和 [2, 2]。当你删除一个元素时，就像是放置了一个虚拟的分隔符。第一个或最后一个位置的分隔符根本不会分隔任何东西。 - danielsto

你可以使用相同的数组，只需要计算总和，将总和除以三并且每个部分不能超过总和/3的值。左指针可以每次增加一个，右指针应该每次减少一个。一旦子总和溢出，就是中断部分。如果leftSum == rightSum，我们只需要检查{leftPointer+1 --- rightPointer-1}之间的中间值的总和是否相同，如果相同则返回true，否则返回false。一旦我们直接将其乘以3而不是取总和，它将变得与已接受的答案相同。 - Mr X

Answer 2

假设第一个和最后一个元素不能被删除，且所有元素均为>0：

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

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

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

3. 如果sumleft > sumright，则将右侧的下一个值添加到sumright中。返回 1。

如果所有元素都被使用，那么就没有解决方案。

编辑：当 sumleft == sumright 时，可以通过首先对所有元素求和（也仅需要 O(n)），并检查此求和减去要删除的元素是否等于sumleft * 3来测试是否满足要求。

- Michael Butscher

---

如果我理解正确的话，这个数组中有两个元素被丢弃了，而它们被丢弃的位置会作为分隔符来将这个数组分成三个较小的子数组（这三个子数组的元素和相等）。 - Michael Butscher

向您致敬，先生。我从他的帖子中完全没有理解，干得好。 - Ali Elgazar

@Danish，你说的第三个元素是什么意思？ - Michael Butscher

@MauricePerry 我无法找到任何解决方案来处理你的示例，无论是使用还是不使用我的算法。 - Michael Butscher

@MichaelButscher 和上面一样：删除4和5。 - Maurice Perry

Answer 3

以下结果更像是一种“蛮力”方法，应该也适用于负数。同时，我们还添加了一种版本，可以删除任意两个项目并按任何索引拆分。尽管这只是伪代码。

如果我们按照这些项拆分数组...

var count = a.Length (a is input)

// we need:
for i=0; i<cnt; i++
sum += a[i]
sumLeft[i] = a[i]; if (i > 0) sumLeft[i] += sumleft[i-1]
sumRight[cnt-1-i] = a[i]; if (i > 0) sumRight[cnt-1-i] += sumRight[cnt-1+1-i]

// calc:
for i=1; i<cnt; i++;
for j=cnt-2; j>i; j--;
if (sumLeft[i-1] == sumRight[j+1-1] == sum - a[i] - a[j] - sumLeft[i-1] - sumRight[j-1]) return true;

otherwise return false aft cycle

如果我们可以取出任意两个项目并在任何位置拆分：

for i=0; i<cnt; i++
for j=i+1; j<cnt; j++
newSum = sum - a[i] - a[j]
if (newSum mod 3 != 0) continue;
if passes check(newSum, i, j, a), return true

return false aft cycle

the check (newSum, dropi, dropj, a):
  thirdSum = newSum / 3

  // summarize from left, until we get the third'sum - if we exceed it, we don't have a result
  leftSum = 0;
  i=0;
  do {
    if (i != dropi && i !- dropj) leftSum += a[i]
    i++;
  } while leftSum < thirdSum
  if (thirdSum != leftSum) return false;

  right = 0;
  i=a.Length-1;
  do {
    if (i != dropi && i !- dropj) rightSum += a[i]
    i++;
  } while rightSum < thirdSum
  if (thirdSum != rightSum) return false;

  return true;

- baHI