pythontip 100days-day35

和最接近的分隔位置

给定一个数组a,返回位置i,使得sum(a[: i + 1])sum(a[i + 1 : ])最接近

如果有多个满足条件的位置,返回最小的那个

例子

nearest_split_sum([7,3,2,8,0,-1,9]) -> 2
nearest_split_sum([1,1,0,1,1]) -> 1
nearest_split_sum([1]) -> 0

假设

  1. 输入的数组不为空

tips

  1. 利用之前的分段和计算新的分段和

解法1:

def nearest_split_sum(a):
    """
    1. 遍历分割点,将队列分为前后两部分
    2. 计算前后两部分的和,然后使用index和diff记录分割点的索引和前后两部分的差值
    3. 比较差值然后改变索引
    :param a:
    :return:
    """
    if not a:
        return -1
    index, diff = 0, 9999999999
    for i in range(len(a)):
        tmp_diff = abs(sum(a[:i + 1]) - sum(a[i + 1:]))
        if tmp_diff < diff:
            diff = tmp_diff
            index = i

    return index