leetcode #1 两数之和
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = dict()
for i, val in enumerate(nums):
dic[val] = i
for i, val in enumerate(nums):
j = dic.get(target-val)
if j and j != i:
return [i, j]
leetcode #15 三数之和
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
ans = list()
# 枚举 a
for first in range(n):
# 需要和上一次枚举的数不相同
if first > 0 and nums[first] == nums[first - 1]:
continue
# c 对应的指针初始指向数组的最右端
third = n - 1
target = -nums[first]
# 枚举 b
for second in range(first + 1, n):
# 需要和上一次枚举的数不相同
if second > first + 1 and nums[second] == nums[second - 1]:
continue
# 需要保证 b 的指针在 c 的指针的左侧
while second < third and nums[second] + nums[third] > target:
third -= 1
# 如果指针重合，随着 b 后续的增加
# 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if second == third:
break
if nums[second] + nums[third] == target:
ans.append([nums[first], nums[second], nums[third]])
return ans
leetcode #15 最接近的三数之和
排序后双指针法
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
best = 10**7
# 根据差值的绝对值来更新答案
def update(cur):
nonlocal best
if abs(cur - target) < abs(best - target):
best = cur
# 枚举 a
for i in range(n):
# 保证和上一次枚举的元素不相等
if i > 0 and nums[i] == nums[i - 1]:
continue
# 使用双指针枚举 b 和 c
j, k = i + 1, n - 1
while j < k:
s = nums[i] + nums[j] + nums[k]
# 如果和为 target 直接返回答案
if s == target:
return s
update(s)
if s > target:
# 如果和大于 target，移动 c 对应的指针
k0 = k - 1
# 移动到下一个不相等的元素
while j < k0 and nums[k0] == nums[k]:
k0 -= 1
k = k0
else:
j0 = j + 1
while k > j0 and nums[j0] == nums[j]:
j0 += 1
j = j0
return best
leetcode #18 四数之和
与三数之和类似
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len(nums) #先排序
if n<4:
return []
nums.sort()
res = []
for i in range(n-3):
if i>0 and nums[i]==nums[i-1]:continue #第一个元素向后遍历时如果和当前元素相等则越过
if nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target:break #如果升序数组前四个数已经比target大，则说明后续不会有结果，直接返回空列表
if nums[i]+nums[n-3]+nums[n-1]+nums[n-2]<target:continue #如果当前第一个元素和最后三个元素之和小于target，第一个元素往后移一位
for j in range(i+1,n-2):
if j>i+1 and nums[j]==nums[j-1]:continue # 第二个元素同理第一个元素
if nums[i]+nums[j+1]+nums[j+2]+nums[j]>target:break
if nums[i]+nums[n-2]+nums[n-1]+nums[j]<target:continue
left,right = j+1,n-1#第三第四个元素同双指针
while left<right:
tmp = nums[i] + nums[j] + nums[left] + nums[right]
if tmp == target: #遇到合法结果，append当前四个元素
res.append([nums[i],nums[j],nums[left],nums[right]])
#left和right分别向右向左走找到与当前第三第四个元素不同的元素
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1
right -= 1
# 如果当前结果大于targe，右指针向左走
elif tmp > target: right -= 1
# 如果当前结果小于target，左指针向右走
else: left += 1
return res
leetcode #49 字母异位词分组
考虑将每个字符串按字母大小排序，之后利用哈希表实现
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
hashmap = dict()
for s in strs:
sorted_s = ''.join(sorted(s))
if sorted_s not in hashmap:
hashmap[sorted_s] = [s]
else:
hashmap[sorted_s].append(s)
return [hashmap[key] for key in hashmap]
leetcode #149
leetcode #219 存在重复元素2
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
hashmap = dict()
for i in range(len(nums)):
if nums[i] not in hashmap:
hashmap[nums[i]] = i
else:
if i - hashmap[nums[i]] <= k:
return True
else:
hashmap[nums[i]] = i
return False
leetcode #220 存在重复元素3
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
if t < 0 or not k or not nums:
return False
if k == 1:
for i in range(len(nums)-1):
if abs(nums[i]-nums[i+1]) <= t:
return True
return False
if not t:
dct = {}
for inx, i in enumerate(nums):
if i in dct:
if inx-dct[i] <= k:
return True
dct[i] = inx
return False
lst = []
i = nums[0]
lst.append(sum([(i-j, i+j) for j in range(t+1)], ()))
for i in nums[1:]:
if i in set(sum(lst, ())):
return True
lst.append(sum([(i-j, i+j) for j in range(t+1)], ()))
lst = lst[-k:]
return False
leetcode #447 回旋镖
class Solution:
def numberOfBoomerangs(self, points: List[List[int]]) -> int:
count = 0
for i in range(len(points)):
hashmap = dict()
x, y = points[i]
for j in range(len(points)):
if i == j:
continue
x_, y_ = points[j]
dis = (x-x_)**2 + (y-y_)**2
if dis not in hashmap:
hashmap[dis] = [j]
else:
hashmap[dis].append(j)
for key in hashmap:
k = len(hashmap[key])
if k >= 2:
count += k * (k-1)
return count
leetcode #454 四数相加2
class Solution:
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
n = len(A)
if n == 0:
return 0
hashmap = dict()
count = 0
for i in range(n):
for j in range(n):
if A[i]+B[j] not in hashmap:
hashmap[A[i]+B[j]] = 1
else:
hashmap[A[i]+B[j]] += 1
for i in range(n):
for j in range(n):
if -(C[i]+D[j]) in hashmap:
count += hashmap[-(C[i]+D[j])]
return count
