删除两个元素将数组平均分成三部分，时间复杂度为 O(n)

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

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

Thanks

• Step 1:创建求和数组

• Step 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;

Note:数组包含从 0 到 n-1 的索引；

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