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

Question

给定一个数字数组，查找是否有方法从数组中删除/移除一个数字，并在数组中进行一个分区（将数组划分为两个子数组），以使子数组1中的元素和等于子数组2中的元素和。

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) =中完成

伪代码：-有效的解决方案包括提前计算阵列中所有元素的总和。然后，对于数组中的每个元素，我们可以通过使用数组元素的总和减去到目前为止找到的元素之和来计算其在O（1）时间内的右和。该解的时间复杂度为O（n），其使用的辅助空间为O（1）。

因此，要解决我们的问题，一种蛮力方法是：-移除每个元素一次，然后检查数组是否可以划分为两个相等和的子数组。因此需要O（n^2）时间。

那么，我们能做得比这个时间复杂度更好吗？

Answer 1

正如RaffleBuffle指出的，当我们遍历不同的分离点时，可能会有一些被删除元素的场景。举个例子，

a a a a a a a a a a a a a a
<-----X--------->|<------->

a a a a a a a a a a a a a a
<--------------->|<---X--->

解决O（n）整体复杂性的一种方法是遍历两次。每次检查两个总和之间的差值是否在我们跟踪我们来自的一方的值映射中。

Python代码：

def f(A):
  values = set()
  total_sum = sum(A)

  # Traverse from left, each part
  # must have at least one element.
  left_sum = A[0]
  right_sum = total_sum - A[0]
  values.add(A[0])

  for i in range(1, len(A) - 1):
    values.add(A[i])
    left_sum += A[i]
    right_sum -= A[i]

    # We have an element in the left part
    # that's the difference between left
    # and right sums.
    if (left_sum - right_sum) in values:
      return True

  # Traverse from right, each part
  # must have at least one element.
  right_sum = A[len(A)-1]
  left_sum = total_sum - A[len(A)-1]
  values.clear()
  values.add(A[len(A)-1])

  for i in range(len(A) - 2, 0, -1):
    values.add(A[i])
    right_sum += A[i]
    left_sum -= A[i]

    # We have an element in the right part
    # that's the difference between right
    # and left sums.
    if (right_sum - left_sum) in values:
      return True

  return False

As = [
  [1, 2, 1, 1, 1], # True
  [1, 1, 1, 2, 1], # True
  [1, 1, 1, 1, 1, 1], # False
  [6, 2, 2, 1, 3]  # True
]

for A in As:
  print("%s\n%s\n\n" % (A, f(A)))

Answer 2

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

下面是一些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;
}