删除两个元素,将数组在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)？

谢谢

Answer 1

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

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

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

2. 如果sumleft < sumright,请从左侧添加下一个值sumleft.回到1.

3. 如果sumleft > sumright,请从右侧添加下一个值sumright.回到1.

如果消耗了所有元素,则没有解决方案.

Answer 2

• 步骤1：创建一个求和数组
• 步骤2：遵循两个指针的方法

• 步骤3：如果有帮助，请对答案进行投票：)

  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
  }