题目描述
给一个整数数组nums和整数x
需要从数组的左边或者右边删除元素，然后用x减去删除的元素
问如果x刚好成删到0，怎么删最短？
基本分析
- 反向思考？找一个最长的子数组满足和= sum(nums) - x
- 为啥可以双指针？（1）元素都是整数，序列和是单调的；（2）元素连续
代码
def minOperations(self, nums: List[int], x: int) -> int:
n = len(nums)
l = 0
target = sum(nums) - x
if target < 0:
return -1
s = 0
ans = -1
for r, x in enumerate(nums):
s += x
while s > target:
s -= nums[l]
l += 1
if s == target:
ans = max(ans, r - l + 1)
if ans < 0:
return -1
else:
return n - ans
总结
- 反向思考
基本分析
- 怎么直接计算？（1）先找到后缀中满足和<=x的最长后缀的索引；（2）枚举前缀l，while中一直往后挪右指针，找到和不大于x的索引，while出来后如果=，更新答案。
代码
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
s, n = 0, len(nums)
# 找到最远的满足后缀和<=x的索引
r = n
while r > 0 and s + nums[r - 1] <= x:
r -= 1
s += nums[r]
# 出来的s不一定就满足>=的要求
if r == 0 and s < x:
return -1
# 出来的值可能会等，可能会>
if s == x:
ans = n - r
else:
ans = inf
for l in range(n):
s += nums[l]
while r < n and s > x:
s -= nums[r]
r += 1
# 出来的s不一定就<=x
if s > x:
break
if s == x:
ans = min(ans, l + 1 + n - r)
if ans == inf:
return -1
else:
return ans
总结
- 在找后缀的时候，r是最远的满足s<=x的的位置
- 为啥出来的r也可能不满足要求？r已经计算到了0，s就是整个元素的和，如果<x, 表示不能删
- 给ans赋初值的时候有啥细节？如果s本身就是一个答案，需要考虑进来，就是n-r。如果不是，因为要求最小值，初值给inf
- 计算结果的思路？枚举左端点，委会两边的和s，这个时候s可能会< = 或者 > x (1)小于时候，继续枚举；（2）=更新答案；（3）> 时候，右指针需要往右（但不能越界），更新s；出来的s可能是<=x的情况，如果是=继续更新答案