删除两个元素以在 O（n）中将数组均匀地拆分为三部分

algorithm java

2022-09-04 05:58:36

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

  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）？

谢谢

答案 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 的索引;

现在，我们将指针彼此移动，并且在每次移动时，我们都会计算leftPartSum，middlePartSum和rightPartSum。我们是需要移动左指针还是右指针，取决于两个总和中的哪一个（leftPartSum或rightPartSum更小）

答案 2

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

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

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

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

编辑：测试何时满足要求可以通过最初汇总所有元素（也只需要）并检查此总和减去要删除的元素是否相等来完成。sumleft == sumrightO(n)sumleft * 3

删除两个元素以在 O（n） 中将数组均匀地拆分为三部分

删除两个元素以在 O（n）中将数组均匀地拆分为三部分