3.21 LeetCode 使用dic解决问题
1. Two Sum
从无序数组中,找到两个数求和为target,返回下标。
字典,数值:索引
避免重复数字被覆盖,先从字典里查找target - nums[i],如果找到则返回,没找到就加入字典。
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = {}
for i in range(len(nums)):
com = target - nums[i]
if com in dic:
return sorted([i, dic[com]])
dic[nums[i]] = i
return []
4Sum II
从分别四个数组里找一个元素,求和为0的可能组合有多少个。
字典,A+B可能的和:和为key的可能组合种数
当n为500时,n^2的时间复杂度可以接受。
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
dic = {}
for i in A:
for j in B:
if i+j not in dic:
dic[i+j] = 1
else:
dic[i+j] += 1
ans = 0
for k in C:
for l in D:
if -k-l in dic:
ans += dic[-k-l]
return ans
Number of Boomerangs
给出二维数组,每个子list表示[x,y]点坐标,求该数组里,存在多少个由这些点构成的三元组(i, j, k),使得i,k两点的距离等于i,j两点的距离。
字典,距离:到某个点距离为key的点的个数
对每个点,求另外两个点,到该点的距离相同
def numberOfBoomerangs(self, points: List[List[int]]) -> int:
ans = 0
for i in points:
dic = {}
for j in points:
if i!=j:
d = self.distance(i,j)
if d not in dic:
dic[d] = 1
else:
dic[d] += 1
for k in dic:
ans += dic[k]*(dic[k]-1)
return ans
def distance(self,i,j):
return (i[0]-j[0])**2 + (i[1]-j[1])**2
总结
如何确定字典的key和value,取决于你想通过字典查找什么信息。