查找4

1、字母异位词分组（49）2、直线上最多的点数（149）3、四数相加II（454）4、回旋镖的数量（447）

1、字母异位词分组（49）

题目描述：

【中等题】 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

题目链接

思路分析：

字母异位词就是两个字符串中的字母都是一样的，只不过顺序被打乱了，这里要把他们找出来，再放到一起。

题解一：排序再判断

既然字母异位词的字母都是一样的，那么对他们排序生成一个新的字符串，如果生成新的字符串相同，那么它们就是字母异位词。

可以设置一个字典，进行键与多值的映射

遍历字符串：

键设置为排序后的单个字符，因键为不可变类型，所以需要将类型改变为元组类型字典值等于字典搜索的键加上当前字符

返回字典中的值

class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: dict={} for item in strs: key=tuple(sorted(item))# 字典的键是不可变类型，所以用tuple,（item排序后为列表数据，为可变类型） dict[key]=dict.get(key,[])+[item] # 值 return list(dict.values())

时间复杂度：$O(NKlogK)$,其中N为字符串的长度，K为字符串中单个字符的最长长度。

空间复杂度：$O(NK)$

知识点：

字典中的键可以是元组，但不能为列表，因为元组是不可变的，而列表是可变的。

python中要求字典中的键是不可变的，如字符串、数字或元组，而值则可以取任何数据类型。

dict.get(key, default=None)

参数 key – 字典中要查找的键。 default – 如果指定键的值不存在时，返回该默认值。

2、直线上最多的点数（149）

题目描述：

【困难题】 给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

题目链接

3、四数相加II（454）

题目描述：

【中等题】

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 $-2^{28}$ 到 $2^{28}$ - 1 之间，最终结果不会超过 $2^{31}-1$ 。

题目链接

思路分析：

将AB和CD分为两组求和，然后利用哈希查找

注意重复值也算，因为是不同数据加出来的，而不同数据是对应不同index。

具体流程如下：

以字典的形式建立哈希表初始结果res=0遍历数组C、D，计算和并存放在哈希表中【键：一组和结果，值：对应键所出现的次数。】遍历数组A、B，在哈希表中查找-A-B，如果存在，则结果加上其值。 class Solution: def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int: hashmap={} #key=和，value=频率 for c_num in C: for d_num in D: hashmap[c_num+d_num]=hashmap.get(c_num+d_num,0)+1 res=0 for a_num in A: for b_num in B: s=0-a_num-b_num if s in hashmap.keys(): res+=hashmap[s] return res 时间复杂度：$O(n^2)$空间复杂度：$O(n^2)$

4、回旋镖的数量（447）

题目描述：

【简单题】

给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。

找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。

题目链接

思路分析：

回旋镖就是以i为枢纽，考虑其他点到i的距离

本题典型的排列组合问题，因为题中说可以改变顺序，那么就需要用排列公式Anm = n * m

因为要求距离相等，我们知道距离的平方也会相等，所以将不开根号的结果传入map中就可以了

最后遍历已经存储的keySet，再利用排列公式输出结果即可。

class Solution: def numberOfBoomerangs(self, points: List[List[int]]) -> int: res=0 # 初始结果为0 for x in points: hashdis={} # key=距离，value=频率 for y in points: i=x[0]-y[0] j=x[1]-y[1] dis=i*i+j*j#计算距离的平方 hashdis[dis]=hashdis.get(dis,0)+1 for item in hashdis.values(): res+=item*(item-1) return res 时间复杂度：$O(n^2)$空间复杂度：$O(n)$