有关哈希表的LeetCode做题笔记，Python实现
15. 三数之和 3Sum
第一种方法：三重遍历，时间复杂度为O(n^3)
第二种方法：两重遍历得到前两个数，然后查询第三个数-(a+b)是否存在。用哈希表set()
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) < 3:
return []
nums.sort()
res = set()
for i, v in enumerate(nums[:-2]) :
if i >= 1 and v == nums[i-1]:
continue
d = {}
for x in nums[i+1:]:
if x not in d:
d[-(v+x)] = 1
else:
res.add((v, -(v+x), x))
return map(list, res)
第三种方法：先升序排序，一遍遍历，然后在后面的新数组里用双指针检查三个数之和是否为0，大于0则右指针向左走，小于0则左指针向右走。
class Solution(object):
def threeSum(self, nums):
if len(nums) < 3:
return []
nums.sort()
res = []
for i, x in enumerate(nums[:-2]):
if i >= 1 and x == nums[i-1]:
continue
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
res.append((nums[i], nums[l], nums[r]))
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r -= 1
return res
