Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一列数,每次去掉开头或者结尾的几个数,问最少去掉几次,去掉的数之和等于给定值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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理