Problem: 454. 四数相加 II
思路
讲述看到这一题的思路
- 思考: 如何用map有效节省时间
想一想: 题目1.两数之和, 用的map
- 推广: 可以时间O(n^3),空间O(n)
map: key=sum123, val=times
- 推广: 时间O(n^2), 空间O(n^2)
两两构建map: key=sum12, val=times
遍历一个map, 检索另一个
- 优化: 时间O(n^2), 空间O(n^2)
构建1个map: key=sum12, val=times
遍历一个map, 检索另一个
知识补充
- 补充: dict.get(key, 缺省值)
Code
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
m = {} # 存储
# 遍历nums1和nums2构建map
for i in nums1:
for j in nums2:
if i+j not in m:
m[i+j] = 1
else:
m[i+j] += 1
n = 0
# 遍历nums3和nums4并且检索map
for i in nums3:
for j in nums4:
n += m.get(-i-j, 0) # 补充: dict.get(key, 缺省值)
return n
Problem: 383. 赎金信
思路
讲述看到这一题的思路
用len=26的数组l: idx表示alpha, val表示个数
遍历magazine, 得到l
遍历ransomNote, 对应l项--, 若对应项为0则false
复杂度
- 时间复杂度:
添加时间复杂度, 示例： $O(n)$
- 空间复杂度:
添加空间复杂度, 示例： $O(n)$
Code
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
# 用len=26的数组l: idx表示alpha, val表示个数
# 遍历magazine, 得到l
# 遍历ransomNote, 对应l项--, 若对应项为0则false
# 构建hash
l = [0] * 30
for ch in magazine:
l[ord(ch) - ord('a')] += 1
# 检索
for ch in ransomNote:
if l[ord(ch) - ord('a')] > 0:
l[ord(ch) - ord('a')] -= 1
else:
return False
return True
Problem: 15. 三数之和
时间
644 ms
击败
70.10%
内存
18 MB
击败
21.40%
思路
讲述看到这一题的思路
思路: 双指针, 时间O(n^2)
-
进行排序
-
双指针: first,mid,end
遍历first, 向后移动mid或者向前移动end
重点:如何去重
因为已经sort 所以可以直接通过移动, 排除掉连续相同的数
复杂度
- 时间复杂度:
添加时间复杂度, 示例： $O(n^2)$
- 空间复杂度:
添加空间复杂度, 示例： $O(n)$
Code
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 思路: 双指针, 时间O(n^2)
# 1.进行排序
# 2.双指针: first,mid,end
# 遍历first, 向后移动mid或者向前移动end
# 重点:如何去重
# 因为已经sort
# 所以可以直接通过移动, 排除掉连续相同的数
# 先进行排序
nums.sort()
print(nums)
l = []
# 遍历
first = 0
while first < len(nums) - 2:
if nums[first] > 0: # 因为非递减 => first大于0, 不可能总和等于0
return l
# 初始化双指针
mid = first + 1
end = len(nums) - 1
while end > mid:
# 移动双指针
if nums[first]+nums[mid]+nums[end] < 0:
mid += 1
continue
if nums[first]+nums[mid]+nums[end] > 0:
end -= 1
continue
if nums[first]+nums[mid]+nums[end] == 0:
print("find:",first,mid,end)
# 在找到3元组之后再进行去重
while end > 0 and nums[end] == nums[end - 1]:
end -= 1
while mid < len(nums)-1 and nums[mid] == nums[mid + 1]:
mid += 1
l.append([nums[first],nums[mid],nums[end]])
# 共同向中间移动
mid += 1
end -= 1
# 对于first进行去重
while first < len(nums)-1 and nums[first] == nums[first + 1]:
first += 1
first += 1
return l
Problem: 18. 四数之和
Code
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
l = []
i = 0
while i < len(nums)-3:
print()
print("i=",i)
if nums[i] > 0 and nums[i] > target: # 剪枝
return l
j = i+1
while j < len(nums)-2:
if nums[i]+nums[j] > 0 and nums[i]+nums[j] > target: # 剪枝
break
left = j+1
right = len(nums)-1
# 双指针
while left < right:
if nums[i]+nums[j]+nums[left]+nums[right] > target:
right -= 1
continue
elif nums[i]+nums[j]+nums[left]+nums[right] < target:
left += 1
continue
else: # 找到了, 进行去重
l.append([nums[i],nums[j],nums[left],nums[right]])
while left < len(nums)-1 and nums[left] == nums[left+1]:
left += 1
while right > left and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
# j去重
while j < len(nums)-1 and nums[j] == nums[j+1]:
j += 1
j += 1
# i去重
while i < len(nums)-1 and nums[i] == nums[i+1]:
i += 1
i += 1
return l