---
image: https://leetcode.com/static/images/LeetCode_Sharing.png
tags: leetcode
---
# Week.3.MID [167. Two Sum II - Input Array Is Sorted]
---
- 1維, 遞增數列, 找出1 <= index1 <= index2, 的兩個index加起來數字等於target
- 僅有一解, return [index1, index2], 不可為同一個index
---
1. 類似two sum, 將target減去數列, 搜尋另一個值, 不過有大小條件
2. 用傳統for loop 會在超大list時做到爆掉
3. 必須得用雙指針來進行
---

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 1維, 遞增數列, 找出1 <= index1 <= index2, 的兩個index加起來數字等於target
        # 僅有一解, return [index1, index2], 不可為同一個index
        # 類似two sum, 將target減去數列, 搜尋另一個值, 不過有大小條件
        if not numbers: return []
        
        # 傳統方式for loop 會出現 Time Limit Exceeded
        # for index,n in enumerate(numbers):
        #     m = target - n
        #     if m == n: return [index+1, index+2]
        #     if m in numbers: return [index+1, numbers.index(m)+1]

        # 用雙指針的方式進行, p1從頭, p2從尾
        p1 ,p2 = 0, len(numbers)-1
        
        while numbers[p1] + numbers[p2] != target: # 做到數字和與target相同
            if numbers[p1] + numbers[p2] < target:
                p1 += 1 # 數字和太小, 小指針往大數字走
            else:
                p2 -= 1 # 數字和太大, 大指針往小數字走
        return [p1+1, p2+1]

[167. Two Sum II - Input Array Is Sorted]:https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/