今天的题目涉及到了哈希表与双指针的应用
解法：选择字典作为哈希表，key和val分别用来表示两个数组所有元素的组合之和及其出现的次数。
class Solution(object):
def fourSumCount(self, nums1, nums2, nums3, nums4):
"""
:type nums1: List[int]
:type nums2: List[int]
:type nums3: List[int]
:type nums4: List[int]
:rtype: int
"""
n = len(nums1)
res = dict()
ans = 0
for i in range(n):
for j in range(n):
if nums1[i] + nums2[j] not in res:
res[nums1[i] + nums2[j]] = 1
else:
res[nums1[i] + nums2[j]] += 1
for k in range(n):
for l in range(n):
num = nums3[k] + nums4[l]
if -num in res:
ans += res[-num]
return ans
解法：字符串都由小写字母组成，可初始化长度为26的数组作为哈希表来记录每个字母出现的次数。
class Solution(object):
def canConstruct(self, ransomNote, magazine):
"""
:type ransomNote: str
:type magazine: str
:rtype: bool
"""
cnt = 0
for i in ransomNote:
if i in magazine:
cnt += 1
magazine = magazine.replace(i, '-', 1)
if cnt == len(ransomNote):
return True
else:
return False
解法：同一个数组，i，j，k三个下标互不相同，且返回所有不重复的三元组答案。使用哈希表法的难点在于去重，去重的操作又是比较困难的，因此不推荐使用哈希表法。本题可以使用双指针法。具体操作：
1,将数组排序
2.写一层for循环，i从下标0开始到下标末尾。初始化left为i+1，right指向数组结尾，问题就变为求nums[i] + nums[left] + nums[right]的和了（代指为abc）。
3.进行剪枝去重操作：因为已经将数组按从小到大的顺序排序了，如果第一个最小的元素都大于零，说明此后的所有组合都不可能使三数之和等于零了。另外就是a的去重，a是nums里遍历的元素，那么应该直接跳过去。但这里有一个问题，是判断 nums[i] 与 nums[i + 1]是否相同，还是判断 nums[i] 与 nums[i-1] 是否相同。都是和 nums[i]进行比较，是比较它的前一个，还是比较他的后一个呢？如果与后一个比较，那么会把三元组中出现重复元素的情况pass了。我们要做的是 不能有重复的三元组，但三元组内的元素是可以重复的，因此是和前一个元素比较。
4.接下来就是移动left和right了如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans = []
nums.sort()
n = len(nums)
for i in range(n):
left = i + 1
right = n - 1
if nums[i] > 0:
break
if i > 0 and nums[i-1] == nums[i]:
continue
while left < right:
total = nums[i] + nums[left] + nums[right]
if total > 0:
right -= 1
elif total < 0:
left += 1
else:
ans.append([nums[i], nums[left], nums[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
return ans
解法：与三数之和采取一样的办法。只不过多了一层for循环。
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums.sort()
res = []
n = len(nums)
for i in range(n):
if i > 0 and nums[i] == nums[i-1]: continue
for j in range(i+1, n):
if j > i+1 and nums[j] == nums[j-1]: continue
left, right = j+1, n-1
while left < right:
total = nums[i] +nums[j] + nums[left] + nums[right]
if total > target: right -= 1
elif total < target: left += 1
else:
res.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while right > left and nums[right] == nums[right-1]: right -= 1
left += 1
right -= 1
return res
|