# **Leetcode筆記(Two Sum)**

:::info
:information_source: 題目 : Two Sum, 類型 : arrays , 等級 : easy
日期 : 2023/02/17，2023/04/24，2023/06/26，2023/10/29，2023/11/30，2025/02/18
:::

第一次嘗試，複雜度O(n^2^)

class Solution:
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            for j in range(len(nums)):
                if nums[i] + nums[j] == target and i!=j :
                    return i,j

2023/04/24

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        res = []

        for i, num in enumerate(nums):
            
            if (target - num) in hashmap:
                
                res.append(hashmap[target - num])
                res.append(i)

            # 如果先把數字加進hashmap 那就可能找到自己
            hashmap[num] = i

        return res

2023/06/26

ditc.items()  可以同是印出key和value
key in dict 只能拿出key

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = {}
        for i, c in enumerate(nums):
            if (target - c) in record:
                return [i, record[target - c]]
            record[c] = i

2023/10/29

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = {}
        for i, c in enumerate(nums):
            if (target - c) in record:
                return [i, record[target - c]]
            record[c] = i

2023/11/30

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i, n in enumerate(nums):
            if n in hashmap:
                return [i, hashmap[n]]
            hashmap[target - n] = i

2025/02/18

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = collections.defaultdict(int)
        for i, n in enumerate(nums):
            if target - n in record.keys():
                return [i, record[target - n]]
            record[n] = i

---
### **優化**
使用hash map，即dictionary，複雜度O(n)

class Solution:
    def twoSum(self, nums:List[int], target:int) -> List[int]:
        hashMap = {} 
        for i, val in enumerate(nums):
            diff = target - val
            if diff in hashMap: # 注意為用diff去hashMap找
                return i, hashMap[diff]
            hashMap[val] = i  

---

**錯誤語法**
:::warning
:warning: 沒有括號range(len(nums))，等於為==，and為and，for和if都要冒號
:::

**學習**
:::success
:thumbsup: for i, val in enumerate(List)可以被跌代，dict[val] = i，if val in dict:
:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=KLlXCFG5TnA
Provided by. NeetCode

###### tags: `arrays` `easy` `leetcode`