技术岗位 · Coding

恰删一个元素后存在Pivot:从保留的枢轴反推删值

允许负数,pivot左和等于右和,不能把删掉的位置当枢轴。

题目重点:允许负数,pivot左和等于右和,不能把删掉的位置当枢轴。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 删除恰一个下标,剩余顺序不变;pivot自身不计左右和。
  • 空数组或删后为空无pivot;返回是否存在,不需输出删除位置。

解题路线

  1. 枚举每个保留枢轴x,原左和L、右和R。若删左边值v,需要L−v=R,即v=L−R;删右边则v=R−L。
  2. before/after多重计数分别表示枢轴严格左/右存在的值。先从after移除当前x,查询两个目标,最后加入before。
  3. 计数而非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的条件?
✓已复制微信号!