java - 删除两个元素以在 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

• 第一步:创建求和数组

• 第 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)中哪个较小