給出一列數(shù),每次去掉開頭或者結(jié)尾的幾個(gè)數(shù),問最少去掉幾次,去掉的數(shù)之和等于給定值x,兩個(gè)游標(biāo),右側(cè)游標(biāo)從左向右,左側(cè)游標(biāo)也不斷向右掃,同時(shí)保存當(dāng)前情況下去掉的最少的數(shù)的個(gè)數(shù)
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