leetcode #1 兩數(shù)之和
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 三數(shù)之和
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
ans = list()
# 枚舉 a
for first in range(n):
# 需要和上一次枚舉的數(shù)不相同
if first > 0 and nums[first] == nums[first - 1]:
continue
# c 對應的指針初始指向數(shù)組的最右端
third = n - 1
target = -nums[first]
# 枚舉 b
for second in range(first + 1, n):
# 需要和上一次枚舉的數(shù)不相同
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 后續(xù)的增加
# 就不會有滿足 a+b+c=0 并且 b<c 的 c 了，可以退出循環(huán)
if second == third:
break
if nums[second] + nums[third] == target:
ans.append([nums[first], nums[second], nums[third]])
return ans
leetcode #15 最接近的三數(shù)之和
排序后雙指針法
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
best = 10**7
# 根據(jù)差值的絕對值來更新答案
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 四數(shù)之和
與三數(shù)之和類似
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 #如果升序數(shù)組前四個數(shù)已經比target大，則說明后續(xù)不會有結果巴帮，直接返回空列表
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 字母異位詞分組
考慮將每個字符串按字母大小排序痘番，之后利用哈希表實現(xiàn)
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 四數(shù)相加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
