[算法] LeetCode 1.两数之和（python）

ゞ浴缸里的玫瑰 2021-11-16 05:30 187阅读 0赞

题目：  
![1719455-20190730144018818-770793890.png][]

## 1、朴素解法 ##

#### 1.1 最朴素的两个for循环大法： ####

时间复杂度O(n2)

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range(i+1,len(nums)): if nums[i] + nums[j] == target: return [i, j]

![1719455-20190729134859506-1579006237.png][]

但注意，不要用enumerate函数写，会超时：

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: size = len(nums) for i, m in enumerate(nums): j = i+1 while j < size : if nums[i] + nums[j] == target: return [i, j] else: j+=1

![1719455-20190729134905099-1014548264.png][]

#### 1.2 用in优化（表面一个循环） ####

python大法好：用list+in方法，只需要一个for循环就能解决问题了（但其实是python的in帮我们做了一个查找的循环）  
时间复杂度O(n2)

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): if target-nums[i] in nums: if i != nums.index(target-nums[i]): return [i, nums.index(target-nums[i])]

![1719455-20190729134911449-1302309669.png][]

## 3、python字典模拟hash（两遍哈希） ##

时间复杂度O(n)

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: _dict = {} for i, m in enumerate(nums): _dict[m] = i for i, m in enumerate(nums): j = _dict.get(target - m) if j is not None and i != j: return [i, j]

## 4、python字典模拟hash（一遍哈希） ##

时间复杂度O(n)

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: d = {} for i in range(len(nums)): a = target - nums[i] if nums[i] in d: return d[nums[i]],i else: d[a] = i

![1719455-20190729135031532-413476486.png][]

自己想想写写就明白了，字典d里键值对 \{k:v\}的含义是，与k能凑成target的值在nums中的位置为v。（即nums\[i\]=k时，nums\[v\]+num\[i\]=target。）  
边在字典中记下互补这个位置（value）所需互补数（key）边遍历nums数组，之后的遇到nums\[i\]=之前记录的某个互补数时就是找到了，返回他的位置（value）和 i 就完成了。  
![1719455-20190729135658349-920155320.jpg][]

转载于:https://www.cnblogs.com/importGPX/p/11263450.html

[1719455-20190730144018818-770793890.png]: /images/20211116/2e6e8c0287094a6f9657b812916df771.png
[1719455-20190729134859506-1579006237.png]: /images/20211116/08a9c2073c91443caaa195e91cd8c101.png
[1719455-20190729134905099-1014548264.png]: /images/20211116/66f64de9a4354a4f87bc723a45cf41bd.png
[1719455-20190729134911449-1302309669.png]: /images/20211116/3c4c64fb80cb467b8b6f23e9d0545bf1.png
[1719455-20190729135031532-413476486.png]: /images/20211116/34b1197a29a24bd6a2e068af49126296.png
[1719455-20190729135658349-920155320.jpg]: /images/20211116/41802e4cf73a4a0fa5cec5a2192e5310.png