题目重点:允许负数,pivot左和等于右和,不能把删掉的位置当枢轴。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 删除恰一个下标,剩余顺序不变;pivot自身不计左右和。
- 空数组或删后为空无pivot;返回是否存在,不需输出删除位置。
解题路线
- 枚举每个保留枢轴x,原左和L、右和R。若删左边值v,需要L−v=R,即v=L−R;删右边则v=R−L。
- before/after多重计数分别表示枢轴严格左/右存在的值。先从after移除当前x,查询两个目标,最后加入before。
- 计数而非set方便重复删除当前值;查询不能把pivot本身误视为可删候选。该枚举覆盖任意合法“删位+保留pivot”。
手动走一遍
[1,2,1,1]以值2为pivot时L=1、R=2,右侧有1可删,剩[1,2,1]合法。[0]删除后空,无解;[0,0]删一个后剩单0,左右皆0,有解。
Python 参考实现
下面的代码按上文假设实现,适合本地运行并追加自己的测试用例。
代码区可横向滚动;使用键盘时,先聚焦代码区再按方向键查看。
from collections import Counter
def possible_pivot(a):
total, left = sum(a), 0
before, after = Counter(), Counter(a)
for x in a:
after[x] -= 1
if not after[x]:
del after[x]
right = total - left - x
# Preserve x as pivot; remove one value from strictly before or after it.
if before.get(left - right,0) or after.get(right - left,0):
return True
before[x] += 1
left += x
return False
复杂度
期望O(n)时间、O(d)空间,d不同值数量;数值有符号,不能靠单调双指针代替。
易错点与追问
容易失分的边界
- 选择删掉pivot再继续沿原L/R比较,会失去合法保留枢轴的证明。
- 必须按严格左右集合查询,零值重复也要正确处理。
继续深挖
- 返回删位和pivot的新下标,怎样保存各值位置?
- 允许最多删一个时,怎样加入原数组已存在pivot的条件?
