首页 > 代码库 > 两头指针问题
两头指针问题
Minimum Size Subarray Sum**
Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn‘t one, return 0 instead.
看着不难，但是本题的实现起来还会遇到许多的困难
方法一：两头指针，首先遍历数组找到第一个和大于等于目标值的位置，如果到最后都没找到，则返回0，如果开始结束在同一位置，则返回1，然后可得到start和结束位置。之后就是两个指针的移动问题。减去nums[start]之后，如果任大于等于s，那么start++，否则start++,end++,因为那个长度的已经有保证了。注意这里加的时候避免end越界问题。由于end到达最后任然需要继续循环，所以不能使用end作为循环结束的条件，这里使用一个变量i作为循环结束的条件。
1 class Solution(object): 2 def minSubArrayLen(self, s, nums): 3 """ 4 :type s: int 5 :type nums: List[int] 6 :rtype: int 7 """ 8 sum = 0 9 length = len(nums)10 if length == 0:11 return 012 i = 013 for i in range(length):14 sum += nums[i]15 if sum >= s:16 break17 else:18 return 019 start = 020 end = i21 while i < length:22 if start == end:23 return 124 sum -= nums[start]25 if sum >= s:26 start += 127 elif end < length -1:28 start += 129 end += 130 sum += nums[end]31 i += 132 else:33 i += 134 return end - start + 135
方法二：首先遍历一遍数组，每个位置上的值为前边所有值得累加和。然后对每个位置使用二分来查找最后一个差大于等于s的位置。
1 class Solution(object): 2 def minSubArrayLen(self, s, nums): 3 """ 4 :type s: int 5 :type nums: List[int] 6 :rtype: int 7 """ 8 length = len(nums) 9 if length == 0:10 return 011 12 for i in range(1,length):13 nums[i] += nums[i - 1]14 if nums[length - 1] < s:15 return 016 result = length17 for i in range(length):18 """19 找到以i结尾的最短的满足条件的位置，也就是最后一个累加和小于等于nums[i] - s的位置20 """21 if nums[i] < s:22 continue23 j = self.helper(nums,i,nums[i] - s)24 result = min(result, i - j)25 return result26 def helper(self,nums, i, target):27 start = 028 end = i29 while start + 1 < end:30 mid = (start + end) // 231 if nums[mid] <= target:32 start = mid33 else:34 end = mid35 if nums[end] <= target:36 return end37 elif nums[start] <= target:38 return start39 else:40 return -1
两头指针问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。