leetcode算法：Two Sum II

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

这道题描述的是：

给我们一个 非降序的数组 和一个 目标值

要我们在数组中找到两个数的索引位置， 这两个数满足相加的值是目标值

并且案例保证一定有唯一的答案。不会出现多个和无解

要求数组中每个元素只能使用一次！

我的思路：

因为答案是唯一的，不会出现多个也不会没有所以省去很多步骤。

我从start（初始为0）和 last(最后一个位置) 向中间找

如果相加大于目标 last左移

如果相加小于目标 start右移

相等的时候返回 start 和 end

我的python代码：

 1 class Solution(object):
 2     def twoSum(self, numbers, target):
 3         """
 4         :type numbers: List[int]
 5         :type target: int
 6         :rtype: List[int]
 7         """
 8         start, end = 0 , len(numbers) - 1
 9         while True:
10             if numbers[start] + numbers[end] > target :
11                 end -= 1
12             elif numbers[start] + numbers[end] < target :
13                 start += 1
14             else :
15                 break
16         return (start+1 , end+1 )
17 
18 
19 if __name__ == '__main__':
20     s = Solution()
21     res = s.twoSum([2,3,4],6)
22     print(res)