分而治之 - 获取零和切片的数量

Question

我对我写的一段代码有疑问。这是为了获得数组中片数的合计为零。不过，我希望能够使用递归在Python中执行此操作。请看看我的代码，并让我知道，如果你看到的东西关闭。与迭代方法相比，我没有得到正确答案。

def sumzeros(A, low, mid, high): 
    leftsum = 0 
    rightsum = 0 
    counter = 0 

    for i in range(low, mid+1): 
     leftsum += A[i] 

    for j in range(mid+1, high+1): 
     rightsum += A[j] 

    if leftsum + rightsum == 0: 
     counter += 1 

    return counter 


def solution(A, low, high): 
    if low == high: 
     if A[low] == 0: 
      return 1 
     else: 
      return 0 
    else: 
     mid = (low + high) // 2 

     left = solution(A, low, mid) 
     right = solution(A, mid+1, high) 
     cross = sumzeros(A, low, mid, high) 

     return cross + left + right 

print('Recursive solution: Number of sum zeros = {}'.format(solution(A, 0, len(A) - 1))) 

Answer 1

使用MID =（低+高）/ 2或MID =高 - （高 - 低）/ 2