解析
1. Two Sum
# brute force
# - time: O(n2)
# - space: O(1)
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
# sort + 双指针
# - time: O(nlogn)
# - space: O(n)
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
A = [] # 记录排序前，元素num 的原始索引（因为结果中需要返回原始索引）
for i, num in enumerate(nums):
A.append([num, i])
A.sort() # A 将按照每个二元组的第一个元素（即数值）从小到大排序
i, j = 0, len(nums) - 1 # i 指向数组左端（最小值），j 指向数组右端（最大值）
while i < j:
cur = A[i][0] + A[j][0]
if cur == target:
return [A[i][1], A[j][1]]
elif cur < target:
i += 1
else:
j -= 1
return []
# hashmap
# - time: O(n)
# - space: O(n)
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
prevMap = {} # prevMap 中存储的都是可以被考虑的数字
for i, v in enumerate(nums):
diff = target - v
if diff in prevMap:
return [prevMap[diff], i]
prevMap[v] = i
- https://www.youtube.com/watch?v=KLlXCFG5TnA&ab_channel=NeetCode
- https://neetcode.io/problems/two-integer-sum
167. Two Sum II - Input Array Is Sorted
# brute force
# - time: O(n^2)
# - space: O(1)
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if numbers[i] + numbers[j] == target:
return [i + 1, j + 1]
return []
# 左右指针（双指针）
# - time: O(n)
# - space: O(1)
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
l, r = 0, len(numbers) - 1
while l < r:
cur_sum = numbers[l] + numbers[r]
if cur_sum == target:
return [l + 1, r + 1]
elif cur_sum > target:
r -= 1
else:
l += 1
ref
- https://neetcode.io/problems/two-integer-sum-ii
- https://www.youtube.com/watch?v=cQ1Oz4ckceM&ab_channel=NeetCode
15 3Sum
- 排序后，如何保证插入结果集的triplet不重复？
- Approach 1: 用一个set来记录已经插入结果集的triplet，如果当前triplet已经存在于set中，那么就跳过该triplet
- Approach 2:
- 对于左边的指针，
if (i > 0 && nums[i] == nums[i - 1]) continue;- 比如 [-2, -2, 0, 2] 的情况，如果不加这个判断，那么就会发生结果集中有两个重复的[-2, 0, 2] triplet 的情况
- 对于中间的指针，
while nums[m] == nums[m-1] m += 1- 比如 [-2, 0, 0, 2, 2] 的情况，如果不加这个判断，那么会出现结果集中有两个重复的[-2, 0, 2] triplet的情况
- 对于左边的指针，
# burte force
# - time: O(n3)
# - space: O(n) // 解决重复 triplet 的问题
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = set()
nums.sort()
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
for k in range(j + 1, len(nums)):
if nums[i] + nums[j] + nums[k] == 0:
tmp = [nums[i], nums[j], nums[k]]
res.add(tuple(tmp))
return [list(i) for i in res]
# 左右指针（双指针）- with extra space
# - time: O(n2)
# - space: O(n)
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort() # time: O(nlogn), space: O(1)/O(n)
s = set()
# time: 0(n * n)
for i in range(len(nums) - 2):
l, r = i + 1, len(nums) - 1
while l < r:
cur_sum = nums[i] + nums[l] + nums[r]
if cur_sum == 0:
s.add(tuple([nums[i], nums[l], nums[r]]))
r -= 1
l += 1
elif cur_sum > 0:
r -= 1 # move r to the left, to decrease cur_sum
else:
l += 1 # move l to the right, to increase cur_sum
res = []
for triplet in s:
res.append(list(triplet))
return res
# 左右指针（双指针）- without extra space
# - time: O(n2)
# - space: O(1)
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort() # time: O(nlogn), space: O(1)/O(n)
res = []
# time: 0(n * n)
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]: # to skip duplicates, e.g., [-1, -1, 0, 1]
continue
l, r = i + 1, len(nums) - 1
while l < r:
cur_sum = nums[i] + nums[l] + nums[r]
if cur_sum == 0:
res.append([nums[i], nums[l], nums[r]])
r -= 1
l += 1
while l < r and nums[l] == nums[l - 1]: # to skip duplicates, e.g., [-1, 0, 0, 1]
l += 1
elif cur_sum > 0:
r -= 1 # move r to the left, to decrease cur_sum
else:
l += 1 # move l to the right, to increase cur_sum
return res
ref