兩數之和

給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 target 的那 兩個 整數，並返回它們的數組下標。

你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案裡不能重復出現。

你可以按任意順序返回答案。
示例 1：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

輸入：nums = [3,2,4], target = 6
輸出：[1,2]
示例 3：

輸入：nums = [3,3], target = 6
輸出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只會存在一個有效答案
進階：你可以想出一個時間復雜度小於 O(n2) 的算法嗎？

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

暴力破解

• 定義一個列表存儲結果下標。
• 使用雙層循環。
  第一層循環i，
  第二層循環j，從i+1開始。
• 如果 i 等於 target-當前下標為j的值。即兩數相之和等於 target。將下標添加到列表中。
  
  target = 8
  紅色字體：符合目標的值。
  灰色方塊：已循環
  藍色方塊：第一層循環
  橙色方塊：第二層循環

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
res = []
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i] == target - nums[j]:
res.append(i)
res.append(j)
return res
if __name__ == '__main__':
s = Solution()
nums = [3,3]
target = 6
res = s.twoSum(nums,target)
assert res == [0,1]
nums = [3, 2, 4]
tagert = 6
res = s.twoSum(nums,target)
assert res == [1,2]

字典

• 定義一個列表res存儲結果下標。
• 定義一個字典dict，存儲已查找過的值。
  target - nums[0] = 8 - 6 = 2，查找dict，dic中沒有key=2，將dict[nums[0]]=0存入字典
  target - nums[1] = 8 - 3 = 5，查找dict，dic中沒有key=5，將dict[nums[1]]=1存入字典
  target - nums[2] = 8 - 8 = 0，查找dict，dic中沒有key=0，將dict[nums[2]]=2存入字典
  target - nums[3] = 8 - 2 = 6，查找dict，dic中有key=6，將dict[6]、當前index=3存入res列表
  target - nums[4] = 8 - 1 = 7，查找dict，dic中沒有key=7，將dict[nums[4]]=4存入字典
  

#字典
class Solution2:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dict = {
}
res = []
for i,v in enumerate(nums):
if dict.get(target-v) is not None:
res.append(dict[target-v])
res.append(i)
else:
dict[v] = i
return res