代码随想录算法训练营 Day 6
Published:
Q1. LeetCode 454
思路：用哈希表存储数组nums1和nums2所有可能的和与该和出现的次数。然后再将数组nums3和nums4中的数字相加，如果-(num3 + num4)出现在哈希表中，则最终结果加上对应的值
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
hashmap = {}
for num1 in nums1:
for num2 in nums2:
s = num1 + num2
hashmap[s] = hashmap.get(s, 0) + 1
res = 0
for num3 in nums3:
for num4 in nums4:
s = num3 + num4
if -s in hashmap:
res += hashmap[-s]
return res
复杂度分析
时间复杂度：O($n^2$) 空间复杂度：O($n^2$)
Q2. LeetCode 383
解法1: 利用哈希表统计magazine中的各个字母出现次数，然后遍历ransomNote，如果当前字母在哈希表中，则将其值减1。当减到0时，在哈希表中将其删掉。如果遍历过程中出现当前字母未出现在哈希表中，返回False；否则返回True
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
if len(ransomNote) > len(magazine):
return False
hashmap = {}
for c in magazine:
hashmap[c] = hashmap.get(c, 0) + 1
for c in ransomNote:
if c not in hashmap:
return False
hashmap[c] -= 1
if hashmap[c] == 0:
del hashmap[c]
return True
解法2: 用数组替代哈希表
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
if len(ransomNote) > len(magazine):
return False
count = [0] * 26
for c in magazine:
idx = ord(c) - ord('a')
count[idx] += 1
for c in ransomNote:
idx = ord(c) - ord('a')
if count[idx] == 0:
return False
count[idx] -= 1
return True
复杂度分析
时间复杂度：O($n$) 空间复杂度：O(1)
Take some notes
使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。 所以在使用哈希表之前，需要考虑数组是否可行
Q3. LeetCode 15
解法1：第一层循环确定最小数字a，第二层循环确定最大数字c，如果b存在，则必定在两数之间。利用哈希表存储第二次循环中出现的数字，若哈希表中能找到该数字，则组合为结果之一
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
hashmap = {}
nums.sort()
res = []
for i in range(len(nums)):
if nums[i] > 0:
break
# 当前数字和前一个数字相同，则其对应的组合也和之前一致，因此可以跳过
if i > 0 and nums[i] == nums[i - 1]:
continue
appeared_num = {}
for j in range(i + 1, len(nums)):
# 需要判断连续三个数是否相同，而非两个数
if j > i + 2 and nums[j] == nums[j - 1] == nums[j - 2]:
continue
diff = - (nums[i] + nums[j])
if diff in appeared_num:
res.append([nums[i], nums[j], diff])
appeared_num.pop(diff)
else:
appeared_num[nums[j]] = j
return res
复杂度分析
时间复杂度：O($n^2$) 空间复杂度：O($n$)
难点
注意对于三个数字的去重方式，特别是对于c的去重，需要判断连续三个数字是否相同
解法2: 第一层循环确定最小数字a，利用双指针分别求b，c
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i in range(len(nums)):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
j = i + 1
k = len(nums) - 1
while j < k:
s = nums[i] + nums[j] + nums[k]
if s < 0:
j += 1
elif s > 0:
k -= 1
else:
res.append([nums[i], nums[j], nums[k]])
# 对b去重
while j < k and nums[j + 1] == nums[j]:
j += 1
# 对c去重
while j < k and nums[k - 1] == nums[k]:
k -= 1
j += 1
k -= 1
return res
复杂度分析
时间复杂度：O($n^2$) 空间复杂度：O(1)
Q4. LeetCode 18
思路：与Q3类似，只是需要再加一层循环确定第二个数字
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
res = []
nums.sort()
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, len(nums)):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
k = j + 1
l = len(nums) - 1
while k < l:
s = nums[i] + nums[j] + nums[k] + nums[l]
if s < target:
k += 1
elif s > target:
l -= 1
else:
res.append([nums[i], nums[j], nums[k], nums[l]])
while k < l and nums[k + 1] == nums[k]:
k += 1
while k < l and nums[l - 1] == nums[l]:
l -= 1
k += 1
l -= 1
return res
复杂度分析
时间复杂度：O($n^3$) 空间复杂度：O($1$)