arrays - 如果可以删除任何一个元素，则查找是否可以将数组分为相等和的两个子数组

Question

给定一个数字数组，查找是否有办法从数组中删除/删除一个数字并在数组中进行一个分区(将数组划分为两个子数组)，使得 subarray1 中的元素总和等于 subarray2 中元素的总和.

A subarray is a contiguous part of array.
Array [1, 2, 3, 4] has (1), (1,2), (2,3,4),(1,2,3,4) etc.. as its subarrays but not (1,3) , (2,4) , (1,3,4), etc..

现在让我们考虑一个例子:-

(Follow 0-based indexing )
Array[] = [ 6, 2, 2, 1, 3 ]

Possible solutions
Delete Array[0] => updated array: - [ 2,2,1,3 ]
Possible partition              : - [2,2] and [3,1] where (2+2) = (3+1) = 4
or
Delete Array[1] => updated array: - [ 6,2,1,3 ]
Possible partition              : - [6] and [2,1,3] where (6) = (2+1+3) = 6
or
Delete Array[2] => updated array: - [ 6,2,1,3 ]
Possible partition              : - [6] and [2,1,3] where (6) = (2+1+3) = 6

现在一个类似的问题已经存在，我们只需要找到数组是否可以分成两个相等和的子数组，可以在 O(n) =>

PsuedoCode:- The efficient solution involves calculating sum of all elements of the array in advance. Then for each element of the array, we can calculate its right sum in O(1) time by using total sum of the array elements minus sum of elements found so far. The time complexity of this solution would be O(n) and auxiliary space used by it will be O(1).

因此，要解决我们的问题，一种蛮力方法是:- 删除每个元素一次并检查数组是否可以分为两个等和的子数组。因此它将需要 O(n^2) 时间。
那么我们可以做得比这个时间复杂度更好吗？

Answer 1

您可以使用映射来跟踪数组中每个值出现的位置。然后，当您考虑每个分区点在数组中移动时，如果 map 中存在左半部分和右半部分之间的差异，并且在正确的一半中(通过将左右差异与位置比较是正还是负来确定)相对于当前分区点的值)然后你有一个解决方案。
下面是一些 Java 代码来说明:

static boolean splitDelete(int[] a)
{
    Map<Integer, List<Integer>> map = new HashMap<>();
    for(int i=0; i<a.length; i++)
    {
        List<Integer> idx = map.get(a[i]);
        if(idx == null) map.put(a[i], idx = new ArrayList<>());
        idx.add(i);
    }
    
    int sum = 0;
    for(int v : a) sum += v;
            
    int diff = sum;
    for(int i=0; i<a.length-1; i++)
    {
        diff -= 2*a[i];
        if(map.containsKey(Math.abs(diff)))
            for(int j : map.get(Math.abs(diff)))
                if(diff > 0 == j > i) return true;
    }
    
    return false;
}