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 个数相加的问题, 联合二分的思路, 同样能够不便的求解