# 【LeetCode刷題】【演算法學習筆記】相向雙指針 二三數之和

### 167. Two Sum II - Input Array Is Sorted
✎ 題目連結：[Leetcode](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/) / [力扣](https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description/)

:::spoiler 💡思路
1. rerence: [灵茶山艾府]( https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/solution/san-shu-zhi-he-bu-hui-xie-xiang-xiang-sh-6wbq/)
2. 說明：題目給我們一個升序陣列和目標值，找到陣列中的兩數相加等於 ==target==
3. 思路：
✎ 我們可以使用**雙指針** ➡︎ 藉由==left== ==right==調整數字大小，已接近到達目標值。
4. 優點：
* 雙指針 讓我們一次只需要檢查一個數對，而不需要使用兩層迴圈暴力搜尋，時間複雜度是 O(n)，比暴力解法的 O(n²) 快很多。
* 由於 numbers 已經排序好，我們可以利用數值大小的資訊來決定如何移動指針，這是關鍵的優勢。
:::

from typing import List

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 雙指針初始化
        left = 0 
        right = len(numbers) - 1
        
        while True: # 也可以寫成 left < right
            # 計算兩數之和
            sum = numbers[left] + numbers[right]
            # 判斷兩數合大小
            if sum == target:
                break
            # 調整指針位置
            if sum < target:
                left += 1
            elif sum > target:
                right -= 1
                
        return [left+1, right+1] # 下標為 1  

### 15. 3Sum
---
✎ 題目連結：[Leetcode](https://leetcode.com/problems/3sum/) / [力扣](https://leetcode.cn/problems/3sum/description/)

:::spoiler 💡思路
1. rerence: [灵茶山艾府](https://leetcode.cn/problems/3sum/solution/shuang-zhi-zhen-xiang-bu-ming-bai-yi-ge-pno55/ )
2. 說明：二數之和的延伸。從陣列中，找到三個不同的數，相加等於==0==
3. 思路：
1. 以一變數==x==沿用二數之和概念
:::

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 將陣列進行排序
        nums.sort() 
        ans = []
        n = len(nums)

        # x 從 i ~ n-2 進行拜訪
        for i in range(n-2):
            x = nums[i]
            if i > 0 and x == nums[i-1]: # 跳過重複數字
                continue 
            # 優化: 排除陣列皆為正數->陣列前三項皆為正數 
            if x + nums[i + 1] + nums[i + 2] > 0:
                break
            # 優化: 如果 x 加陣列中最大兩數仍小於 0，代表這個 x 太小了，直接 continue 換下一個數
            if x + nums[-2] + nums[-1] < 0: 
                continue

            # 三整數相加
            j = i + 1
            k = n - 1
            while j < k: # True
                sum = x + nums[j] + nums[k]
                if sum > 0:
                    k -= 1
                elif sum < 0:
                    j += 1
                # 三數相加為 0
                else:
                    ans.append([x, nums[j], nums[k]])
                    # 指針 j 向前走
                    j += 1
                    while j < k and nums[j] == nums[j-1]: # 排除重複元素
                        j += 1
                    # 指針 k 向前走
                    k -= 1
                    while j < k and nums[k] == nums[k+1]: # 排除重複元素
                        k -= 1
        return ans