今天刷哈希表。
这题一直没思路，不知道怎么判断返回False的情况。但是重点其实在无限循环这个条件上面。
回想链表题，不论是交点还是有环链表，一般都可以用哈希表来做。比如说找有环链表的入口，只要把指针走过的节点加入哈希表，第二次到达入口的时候就能识别出来了。因此，无限循环的问题用哈希表是很合适的。
def sumOnDigits(n):
if not n:
return 0
return (n % 10)**2 + sumOnDigits(n//10)
class Solution:
def isHappy(self, n: int) -> bool:
sums = set()
i = sumOnDigits(n)
while i != 1:
if i in sums:
return False
sums.add(i)
n = i
i = sumOnDigits(n)
return True
这道题需要注意：为什么哈希表会比暴力法快。
暴力法对于每个元素 i, 在[i+1…j]上遍历查找符合A[i]+A[k] == target 的k。
哈希表免除的是遍历查找的那个O(n)，而不是其他。
这就带到了下一题：
一开始我写出了这样的解法：
def calc(nums3, map3, map4):
for num3 in nums3:
for num4 in map4:
sum = num3 + num4
if sum not in map3:
map3[sum] = map4[num4]
else:
map3[sum] += map4[num4]
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
map1 = {}
map2 = {}
map3 = {}
map4 = {}
for num in nums4:
if num not in map4:
map4[num] = 1
else:
map4[num] += 1
calc(nums3, map3, map4)
calc(nums2, map2, map3)
calc(nums1, map1, map2)
return map1[0] if 0 in map1 else 0
思路如下图。
但是这个解法worst case仍然是O(n^4)（n为数组长度）！worst case是每个sum只出现一次。
问题出在没有使用哈希表的常数时间查找功能，而是把哈希表当数组遍历了。
这题和twosum一样，可以exploit四个数的和为0这个条件。将四个数组分成两组，每一组O(n^2)算出{sum, 次数}map。但最后是一个O（n^2）size的常数查找，所以总的来说还是O(n^2)。
改进后的代码如下：
def calc(nums3, nums4, map3, map4):
for num in nums4:
if num not in map4:
map4[num] = 1
else:
map4[num] += 1
for num3 in nums3:
for num4 in map4:
sum = num3 + num4
if sum not in map3:
map3[sum] = map4[num4]
else:
map3[sum] += map4[num4]
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
map1 = {}
map2 = {}
map3 = {}
map4 = {}
calc(nums3, nums4, map3, map4)
calc(nums1, nums2, map1, map2)
count = 0
for num in map1:
if -num in map3:
count += map1[num] * map3[-num]
return count
可以使用python的Counter类：
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
rc = Counter(ransomNote)
rm = Counter(magazine)
for c in rc:
if c not in rm or rm[c] < rc[c]:
return False
return True
这题和twosum有一个很大的区别：不能输出重复的三元组。twosum里面是只要返回一组符合条件的数字就行了，自然不存在重复的问题。而去重正是本题的难点。
python中其实可以用tuple来去重嗷。list是可变的所以unhashable，不能作为set或者dict的key。
暴力解法O(n^3)可以这么实现。是正确的，但是超时了。
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
s = set()
nums.sort() # 注意必须要先排序一遍，这样才不会同时出现(1,2,-3)和(2,1,-3)这种情况。
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:
t = (nums[i],nums[j],nums[k])
if t not in s:
s.add(t)
for t in s:
res.append(list(t))
return res
再优化就是发现j向右移动时符合条件的k只会减不会增。应用双指针来降低一个n的复杂度。
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
s = set()
nums.sort()
for i in range(len(nums)):
k = len(nums) - 1
for j in range(i+1, len(nums)):
while j < k:
sum = nums[i] + nums[j] + nums[k]
if sum == 0:
t = (nums[i],nums[j],nums[k])
if t not in s:
s.add(t)
break
elif sum < 0: # sum < 0时增j
break
else: # sum > 0时减k
k -= 1
for t in s:
res.append(list(t))
return res
用tuple去重是python的一个hack，普通来讲就利用排序数组的性质即可：
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i in range(len(nums)):
if i > 0 and nums[i-1] == nums[i]:
continue
k = len(nums) - 1
for j in range(i+1, len(nums)):
if j > i+1 and nums[j-1] == nums[j]:
continue
while j < k:
sum = nums[i] + nums[j] + nums[k]
if sum == 0:
res.append([nums[i],nums[j],nums[k]])
break
elif sum < 0:
break
else:
k -= 1
return res
3sum多套一层循环就得了。
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
res = []
nums.sort()
for a in range(len(nums)):
if a > 0 and nums[a-1] == nums[a]:
continue
for i in range(a+1, len(nums)):
if i > a+1 and nums[i-1] == nums[i]:
continue
k = len(nums) - 1
for j in range(i+1, len(nums)):
if j > i+1 and nums[j-1] == nums[j]:
continue
while j < k:
sum = nums[a] + nums[i] + nums[j] + nums[k]
if sum == target:
res.append([nums[a],nums[i],nums[j],nums[k]])
break
elif sum < target:
break
else:
k -= 1
return res