对于此类问题,需要了解的一个很好的数据结构是具有累积和的数组。是原始系列中从到element[j] - element[i]
的总和。如果你有原始系列,累积系列是。原始系列中位置的总和是。对于这个问题,我们只对从 0 开始的总和感兴趣,所以这有点矫枉过正,但同样对其他问题更有用。i
j
[1, 2, 3, 4]
[0, 1, 3, 6, 10]
i
element[i] - element[0]
这是进行累积总和的代码:
def cumulative_sum(series):
s = [0]
for element in series:
s.append(element + s[-1])
return s
鉴于此,我们可以使用以下代码找到枢轴点:
def find_pivot(series):
cs = cumulative_sum(series)
total = cs[-1]
even_total = not (total & 1)
if even_total:
target = total // 2
for i, element in enumerate(cs[1:]):
if element == target:
return i + 1
return -1
请注意,如果我们知道系列总和为奇数,则没有必要尝试除以系列:那么就不存在枢轴点。
或者,您可以find_pivot
这样写:
def find_pivot(series):
cs = cumulative_sum(series)
total = cs[-1]
even_total = not (total & 1)
if even_total:
target = total // 2
try:
return cs.index(target)
except ValueError:
return -1
return -1
它的优点是循环不是在 python 中显式完成,而是在标准库的 C 代码中完成。
试用代码:
def test():
for i in range(1, 30):
test_values = range(i)
j = find_pivot(test_values)
if j >= 0:
print "{0} == {1}".format(test_values[:j], test_values[j:])
我们得到这个输出:
[0] == []
[0, 1, 2] == [3]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] == [15, 16, 17, 18, 19, 20]