1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你能够假如每种输出只会对应一个答案。然而，数组中同一个元素不能应用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
def twoSum(nums: List[int], target: int) -> List[int]: if not nums or len(nums) < 2: return prefix_sum = {} n = len(nums) for i in range(n): if nums[i] in prefix_sum: return [prefix_sum[nums[i]], i] prefix_sum[target-nums[i]] = i工夫复杂度为$O(n)$, 工夫复杂度为$O(n)$
15. 三数之和
给你一个蕴含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不反复的三元组。
留神：答案中不能够蕴含反复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组汇合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
def threeSum(nums: List[int]) -> List[List[int]]: if not nums or len(nums) < 3: return [] nums.sort() n = len(nums) res = [] if nums[0] > 0 or nums[-1] < 0: return res for i in range(n-2): p1 = i + 1 p2 = n - 1 if i - 1 >= 0 and nums[i] == nums[i-1]: continue while p1 < p2: if nums[p1] + nums[p2] + nums[i] < 0: # while p1 < n-1 and nums[p1] == nums[p1+1]: # p1 += 1 p1 += 1 elif nums[p1] + nums[p2] + nums[i] > 0: # while p2 > 0 and nums[p2] == nums[p2-1]: # p2 -= 1 p2 -= 1 elif nums[p1] + nums[p2] + nums[i] == 0: res.append([nums[i], nums[p1], nums[p2]]) # print('done') p1 += 1 p2 -= 1 return res工夫复杂度为$O(n^2)$, 工夫复杂度为$O(1)$
16. 最靠近的三数之和
给定一个包含 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最靠近。返回这三个数的和。假设每组输出只存在惟一答案。
示例：
输出：nums = [-1,2,1,-4], target = 1
输入：2
解释：与 target 最靠近的和是 2 (-1 + 2 + 1 = 2) 。
def threeSumClosest(nums: List[int], target: int) -> int: if not nums or len(nums) < 3: return n = len(nums) nums.sort() res = [] nearest_sum = sum(nums[:3]) if nums[0] >= target: return sum(nums[:3]) if nums[-1] <= target: return sum(nums[-3:]) for i in range(n-2): p1 = i + 1 p2 = n - 1 while p1 < p2: temp = nums[i] + nums[p1] + nums[p2] # print(temp) if abs(temp - target) < abs(nearest_sum - target): # res = [nums[i], nums[p1], nums[p2]] nearest_sum = temp if temp < target: p1 += 1 elif temp > target: p2 -= 1 else: return target return nearest_sum工夫复杂度为$O(n^2)$, 工夫复杂度为$O(1)$
18. 四数之和
给定一个蕴含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不反复的四元组。
留神：
答案中不能够蕴含反复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组汇合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
def fourSum(self, nums: List[int], target: int) -> List[List[int]]: if not nums or len(nums) < 4: return [] n = len(nums) nums.sort() res = [] for i in range(n-3): # 保障nums[i]扭转了 if i > 0 and nums[i] == nums[i-1]: continue for j in range(i+1, n-2): # 保障nums[j]扭转了 if j > i + 1 and nums[j] == nums[j-1]: continue h = j + 1 k = n - 1 while h < k: four_sum = nums[i] + nums[j] + nums[h] + nums[k] if four_sum > target: k -= 1 elif four_sum < target: h += 1 else: res.append([nums[i], nums[j], nums[h], nums[k]]) while h < k and nums[h] == nums[h+1]: h += 1 while h < k and nums[k] == nums[k-1]: k -= 1 k -= 1 h += 1 return res工夫复杂度为$O(n^3)$, 空间复杂度为$O(1)$
49. 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母雷同，但排列不同的字符串。
示例:
输出: ["eat", "tea", "tan", "ate", "nat", "bat"]
输入:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
阐明：
所有输出均为小写字母。
不思考答案输入的程序。
思路1: 暴力解法
两两进行比拟, 判断其是否为异位词
def groupAnagrams(strs: List[str]) -> List[List[str]]: if not strs: return [] if len(strs) < 2: return [strs] # 判断两个词是否为异位词 def isAnagram(s1, s2): if not s1 and not s2: return True if not s1 or not s2 or len(s1) != len(s2): return False return sorted(s1) == sorted(s2) dicts = {} for s in strs: flag = False for w in dicts.keys(): if isAnagram(s, w): dicts[w].append(s) flag = True if not flag: dicts[s] = [s] return list(dicts.values())工夫复杂度为$O(n^2klogk)$, 空间复杂度为$O(nk)$
因为工夫简单度过高并未通过测试
思路2
排序 + 哈希表
def groupAnagrams(strs: List[str]) -> List[List[str]]: if not strs: return [] dicts = {} # 异位词排序之后雷同 for s in strs: sorted_s = ''.join(sorted(s)) if sorted_s in dicts: dicts[sorted_s].append(s) eles: dicts[sorted_s] = [s] return list(dicts.values())工夫复杂度为$O(nklogk)$, 空间复杂度为$O(nk)$
思路3
计数 + 哈希表
def groupAnagrams(strs: List[str]) -> List[List[str]]: if not strs: return [] # from collections import defaultdict dicts = collections.defaultdict(list) for s in strs: # 统计每个字符呈现的个数 arr = [0] * 26 for c in s: arr[ord(c) - ord('a')] += 1 # 异位词只是单词程序产生扭转, 每个单词的计数并未变动 dicts[tuple(arr)].append(s) return list(dicts.values())219. 存在反复元素 II
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至少为 k。
示例 1:
输出: nums = [1,2,3,1], k = 3
输入: true
示例 2:
输出: nums = [1,0,1,1], k = 1
输入: true
示例 3:
输出: nums = [1,2,3,1,2,3], k = 2
输入: false
哈希表记录每个元素呈现的右边界
def containsNearbyDuplicate(nums: List[int], k: int) -> bool: if not nums: return False dicts = {} n = len(nums) flag = False for i in range(n): if nums[i] in dicts: if i - dicts[nums[i]] <= k: # 只有存在就为真 return True # 不论nums[i] 是否在字典中, 都须要更新右边界 dicts[nums[i]] = i return False工夫复杂度为$O(n)$, 空间复杂度为$O(n)$
220. 存在反复元素 III
在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。
如果存在则返回 true，不存在返回 false。
示例 1:
输出: nums = [1,2,3,1], k = 3, t = 0
输入: true
示例 2:
输出: nums = [1,0,1,1], k = 1, t = 2
输入: true
示例 3:
输出: nums = [1,5,9,1,5,9], k = 2, t = 3
输入: false
依据题目, $m, n \in [i, i+k]$范畴内的元素, 只有存在abs(nums[m] - nums[n]) <= t即可
桶
对于数组 [0, 5, 1, 9, 3, 4], t = 3, 设置桶的大小为 4 , 依照nums[i] // 4来构建桶
0, 1, 3 位于同一个桶4, 5 位于同一个桶
9 位于同一个桶
这样保障每一个桶内的元素都相差不会超过t, 先不思考 k 的限度, 存在以下两种状况
- 一个桶中蕴含多个元素
- 如果以后元素与相邻桶中的元素相差小于t
另外, 思考k的限度, 能够应用一个滑动窗口
咱们应用字典来示意桶, 键为桶号, 值为处于该桶的元素
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool: if not nums: return False bucket = {} n = len(nums) bucket_size = t + 1 for i in range(n): num = nums[i] // bucket_size # 如果该桶不为空, 则间接返回True # 每个桶只蕴含一个元素 if num in bucket: return True # 将元素放入桶中 bucket[num] = nums[i] # 查看前一个桶 if num - 1 in bucket and abs(bucket[num - 1] - nums[i]) <= t: return True # 查看后一个桶 if num + 1 in bucket and abs(bucket[num + 1] - nums[i]) <= t: return True # 对索引进行了限度, 保障所有桶内的元素都处于 (i-k, i], 相当于一个固定大小的滑动窗口 if i >= k: bucket.pop(nums[i-k] // bucket_size) return False447. 盘旋镖的数量
给定立体上 n 对不同的点，“盘旋镖” 是由点示意的元组 (i, j, k) ，其中 i 和 j 之间的间隔和 i 和 k 之间的间隔相等（须要思考元组的程序）。
找到所有盘旋镖的数量。你能够假如 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。
示例:
输出:
[[0,0],[1,0],[2,0]]输入:
2解释:
两个盘旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
思路1
哈希表
顺次以数组中的每个元素作为i, 计算残余元素与之的间隔, 并对不同间隔进行计数, 应用字典进行保留
def numberOfBoomerangs(points: List[List[int]]) -> int: if not points or len(points) < 3: return 0 n = len(points) def dist(p1, p2): return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]) res = 0 for i in range(n): dicts = {} for j in range(n): if j == i: continue dis = dist(points[i], points[j]) dicts[dis] = dicts.get(dis, 0) + 1 for _, v in dicts.items(): if v > 1: res += v * (v - 1) return res工夫复杂度为$O(n^2)$, 空间复杂度为$O(n)$
149. 直线上最多的点数
给定一个二维立体，立体上有 n 个点，求最多有多少个点在同一条直线上。
示例 1:
输出: [[1,1],[2,2],[3,3]]
输入: 3
解释:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
示例 2:
输出: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输入: 4
解释:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
上一题中应用字典对不同间隔进行计数, 这题应用字典对不同斜率进行计数
固定两点,
def maxPoints(points: List[List[int]]) -> int: if not points: return 0 if len(points) < 3: return len(points) n = len(points) def slope(p1, p2): if p1[0] == p2[0]: return float('inf') return (p1[1] - p2[1]) / (p1[0] - p2[0]) from collections import Counter for p in points: repeated_cnt = sum([1 for point in points if point == p]) counter = Counter([slope(p, point) for point in points if point != p]) temp = counter.most_common(1)[0][1] + repeated_cnt res = max(res, temp + repeated_cnt) return res 454. 四数相加 II
给定四个蕴含整数的数组列表 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 。所有整数的范畴在 -228 到 228 - 1 之间，最终后果不会超过 231 - 1 。
例如:
输出:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]输入:
2解释:
两个元组如下:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int: if not A: return 0 dicts = {} for a in A: for b in B: # 应用字典保留a + b, 对两数之和进行计数 dicts[a+b] = dicts.get(a+b, 0) + 1 res = 0 for c in C: for d in D: if -(c + d) in dicts: res += dicts[-(c + d)] return res工夫复杂度为$O(n^2)$, 空间复杂度为$O(n)$
该问题能够同样扩大到n个数相加的问题, 联合二分的思路, 同样能够不便的求解