和最接近的分隔位置
给定一个数组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
假设
- 输入的数组不为空
tips
- 利用之前的分段和计算新的分段和
解法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