两头指针问题

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 0
12         i = 0
13         for i in range(length):
14             sum += nums[i]
15             if sum >= s:
16                 break
17         else:
18             return 0
19         start = 0
20         end = i
21         while i < length:
22             if start == end:
23                 return 1
24             sum -= nums[start]
25             if sum >= s:
26                 start += 1
27             elif end < length -1:
28                 start += 1
29                 end += 1
30                 sum += nums[end]
31                 i += 1
32             else:
33                 i += 1
34         return end - start + 1
35

View Code

方法二：首先遍历一遍数组，每个位置上的值为前边所有值得累加和。然后对每个位置使用二分来查找最后一个差大于等于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 0
11         
12         for i in range(1,length):
13             nums[i] += nums[i - 1]
14         if nums[length - 1] < s:
15             return 0
16         result = length
17         for i in range(length):
18             """
19             找到以i结尾的最短的满足条件的位置，也就是最后一个累加和小于等于nums[i] - s的位置
20             """
21             if nums[i] < s:
22                 continue
23             j = self.helper(nums,i,nums[i] - s)
24             result = min(result, i - j)
25         return result
26     def helper(self,nums, i, target):
27         start = 0
28         end = i
29         while start + 1 < end:
30             mid = (start + end) // 2
31             if nums[mid] <= target:
32                 start = mid
33             else:
34                 end = mid
35         if nums[end] <= target:
36             return end
37         elif nums[start] <= target:
38             return start
39         else:
40             return -1

View Code