任务

454. 四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

思路

暴力法的时间复杂度为O(n^4),我们利用dic来优化，首先用dic存储前两个数组中两数之和的出现次数，然后遍历后两个数组，再在前两个数组两数之和dic中找到满足条件的key，得到其次数累加即是最终的结果。

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        result = 0
        from collections import defaultdict
        aPlusbDic = defaultdict(int)
        for i in range(0,len(nums1)):
            for j in range(0,len(nums2)):
                aPlusbDic[nums1[i]+nums2[j]] +=1

        for i in range(0,len(nums3)):
            for j in range(0,len(nums4)):
                sum = nums3[i] + nums4[j]
                if 0-sum in aPlusbDic:
                    result += aPlusbDic[0-sum]
        return result

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

思路

顺其自然的思路是，遍历ransomNote，判断当前字符是否在magazine中，如果在，则拿来一个使用。由快速判断元素是否在集合中想到用哈希表，而由于和次数有关，所以使用字典。将magazine存在dic中，key为字符，value为次数。然后遍历ransomNote，判断每个字符能否在dic中查到，查到后每用到一次就减少一个，如果某个字符没有查到则返回False。

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        from collections import defaultdict
        dic = defaultdict(int)
        for c in magazine:
            dic[c] += 1
        for c in ransomNote:
            if dic[c] > 0:
                dic[c] -= 1
            else:
                return False
        return True

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

思路

本题中针对i,left,rihgt的去重逻辑比较复杂

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()
        size = len(nums)
        for i in range(0,size):
            if nums[i] > 0: return result
            if i>0 and nums[i] == nums[i-1]: #对a去重(如果我和我前一个相等，则不处理当前值，前一个处理过了)
                continue
            left = i+1
            right = size #左闭又开
            while right-left >=2: #至少两个数
                sum = nums[i] +nums[left] + nums[right-1]
                if sum < 0:
                    left = left+1
                elif sum > 0:
                    right = right -1
                else:
                    result.append([nums[i],nums[left],nums[right-1]])
                    while  right-left >=2 and nums[left] == nums[left+1]:  #对b去重，其后一样的值均不处理，直到left到最后一个相等数,但是最多到倒数第二个数（区间至少容纳2个数）
                        left +=1
                    while  right-left >=2 and nums[right-1] == nums[right-2]: #对c去重,其前一样的值均不处理，区间至少容纳2个数
                        right -=1 
                    
                    right-=1 #找到一个答案后，双指针同时推进
                    left+=1
        return result

18. 4Sum

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）

思路

同三数之和，只是多了个循环，另外由于现在的目标值是target而不是0，因此三数之和中用的剪支操作本体无法直接用（即使排序）

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        result = []
        nums.sort()
        size = len(nums)
        for i in range(0,size):
            if i>0 and nums[i] == nums[i-1]: #对a去重(如果我和我前一个相等，则不处理当前值，前一个处理过了)
                continue
            for j in range(i+1,size):
                if j>i+1 and nums[j] == nums[j-1]: #对b去重(如果我和我前一个相等，则不处理当前值，前一个处理过了)
                    continue
                left = j + 1
                right = size
                while right-left >=2: #至少两个数
                    sum = nums[i] +nums[j] +nums[left] + nums[right-1]
                    if sum < target:
                        left += 1
                    elif sum > target:
                        right-=1
                    else:
                        result.append([nums[i],nums[j],nums[left],nums[right-1]])
                        while  right-left >=2 and nums[left] == nums[left+1]:  #对c去重，其后一样的值均不处理，直到left到最后一个相等数,但是最多到倒数第二个数（区间至少容纳2个数）
                            left +=1
                        while  right-left >=2 and nums[right-1] == nums[right-2]: #对d去重,其前一样的值均不处理，区间至少容纳2个数
                            right -=1              
                        
                        left+=1
                        right-=1
        return result

心得体会

今天的最后两道题为三数之和，四数之和并不是用哈希表解决的，而是采用双指针法，在参考代码随想录之前较为难想到解法，采用了固定一个节点（四数之和是固定两个），然后用双指针缩区间的方式统计符合条件的元组。关键点在于如何去重，关于去重的细节还需细细斟酌。