[算法]LeetCode 1.两数之和

LeetCode 1.两数之和(python) 1、朴素解法

最朴素的两个for循环大法:

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]

[算法]LeetCode 1.两数之和

但注意,不要用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

[算法]LeetCode 1.两数之和

2、用 in 优化(一遍for循环?)

python大法好:用in方法,只需要一个for循环就能解决问题了(但其实是python的in帮我们做了一个查找的循环)

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])]

[算法]LeetCode 1.两数之和

3、用python字典(哈希表的算法思想) 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

[算法]LeetCode 1.两数之和

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

[算法]LeetCode 1.两数之和

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpxdds.html