LeetCode#167 Two Sum II - Input array is sorted feat. Two Pointers

2017-09-05
#LeetCode #Python #Two Pointers
程式解題/ LeetCode

問題

給定一個遞增的整數陣列nums(已排序)，其中有兩個數的和會等於目標target，回傳他們的位置，且同個位置不能重複選取。

輸入

numbers = [2, 7, 11, 15]
target = 9

輸出

[1, 2]

方法

這題是LeetCode#1 Two Sums的改版，差別是這題輸入的陣列已經經過排序了，這題還是可以用hash table來解，不過這裡我們要用比較不一樣的方法，叫作two pointers 。

two pointers在這裡的使用方法，就是兩個箭頭分別指向陣列的頭跟尾，藉由將左邊的箭頭向右調整以及右邊的箭頭向左調整，逼近出所要求的值。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def twoSum(self, numbers, target):
        left, right = 0, len(numbers) - 1
        while left < right:
            if numbers[left] + numbers[right] < target:
                left += 1
            elif numbers[left] + numbers[right] > target:
                right -= 1
            else:
                return [left + 1, right + 1]

以下的問題也常常用two pointers來解： 1. 字串、陣列反轉 2. 兩個跑者一快一慢在操場上奔馳，問兩人何時相遇 3. 字串回文(Palindrome)