给出一列数,每次去掉开头或者结尾的几个数,问最少去掉几次,去掉的数之和等于给定值x,两个游标,右侧游标从左向右,左侧游标也不断向右扫,同时保存当前情况下去掉的最少的数的个数
1 #1658
2 #Runtime: 875 ms (Beats 72.22%)
3 #Memory: 24.3 MB (Beats 74.7%)
4
5 class Solution(object):
6 def minOperations(self, nums, x):
7 """
8 :type nums: List[int]
9 :type x: int
10 :rtype: int
11 """
12 tar_sum = sum(nums) - x
13 l = 0
14 t_sum = 0
15 ans = -1
16 for r in range(len(nums)):
17 t_sum += nums[r]
18 while l <= r and t_sum > tar_sum:
19 t_sum -= nums[l]
20 l += 1
21 if tar_sum == t_sum:
22 ans = max(ans, r - l + 1)
23 return len(nums) - ans if ans != -1 else -1
24