代码随想录27期|Python|Day7|454.四数相加II|383. 赎金信|15. 三数之和|18. 四数之和

454.四数相加II

由于不需要去重，所以只需要返回hashmap里全部满足情况的配对即可。（如果需要去重，则需要考虑别的方法）

trick：两两组合遍历。首先嵌套遍历A和B，找出全部的a+b组合构成hashmap；然后嵌套遍历C和D，找出全部hashmap表中满足-（c+d）== a+b的非空value，返回全部的组合的总和。

注意！！这里count统计全部组合的时候不是count++，而是count += value，因为不需要去重。

dict字典实现

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
        """
        hashmap = dict()  # 创建存储已经出现过的a + b的值
        # 遍历a + b，构成map
        for a in nums1:
            for b in nums2:
                if a + b in hashmap:
                    hashmap[a + b] += 1
                else:
                    hashmap[a + b] = 1
        count = 0
        # 遍历c + d找出全部符合a + b == -(c + d)
        for c in nums3:
            for d in nums4:
                if -(c + d) in hashmap:
                    count += hashmap[- (c + d)]  # 注意！！这里应该统计全部的组合情况，所以返回的是全部满足情况的a + b，而不是count ++
        return count

dict字典实现（get函数优化A+B中的判断）

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
        """
        # dict字典实现（get函数优化版）
        hashmap = dict()
        for a in nums1:
            for b in nums2:
                # get()函数的使用：dict.get(key, value)获取当前的value，没有的话就创建key - value:0
                hashmap[a + b] = hashmap.get(a + b, 0) + 1
        count = 0
        for c in nums3:
            for d in nums4:
                if -(c + d) in hashmap:
                    count += hashmap[-(c + d)]
        return count

defaultdict+lamda创建简化版

用lambda创建空的defaultdict实现初始化，get函数获取当前的hashmap里的配对数量。

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
        """
        # defaultdict+lambda创建简化版
        from collections import defaultdict
        record, count = defaultdict(lambda : 0), 0
        for a in nums1:
            for b in nums2:
                record[a +b] += 1
        for c in nums3:
            for d in nums4:
                count += record.get(-(c + d), 0)
        return count

383.赎金信

本题是242题姊妹题，一样的解法。

数组实现

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        # 数组实现
        hashmap = [0] * 26
        
        for char in magazine:
            hashmap[ord(char) - ord('a')] += 1
        
        for char in ransomNote:
            hashmap[ord(char) - ord('a')] -= 1
            if -1 in hashmap:
                return False
        return True

dict字典实现（注意判断语句和更新的的位置）

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        # dict字典实现
        hashmap = {}
        for char in magazine:
            hashmap[char] = hashmap.get(char, 0) + 1
        for char in ransomNote:
            if char not in hashmap or hashmap[char] == 0:
                return False
            hashmap[char] -= 1
        return True

counter实现（简洁）

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        # counter实现（简洁）
        from collections import Counter
        # 逻辑是这样的：Counter相减返回的是多出来的key -- value，但是不会返回缺少的值，所以用resomNote 减去 magazine得到的就是resomNote多出来的，not取反
        return not Counter(ransomNote) - Counter(magazine)

count方法+all函数

count(char)返回列表里值为char的个数，all( )函数返回的是是否全部非空，显然，如果全部Note的字符个数都小于magazine，则返回True。

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        # count方法 + all函数
        return all(ransomNote.count(char) <= magazine.count(char) for char in ransomNote)

15. 三数之和 - 力扣（LeetCode）

双指针法

trick：对数组排序，保证了大的数字都在右边，小的数字都在左边。?

基本思想：固定a（即i），然后遍历a后面的情况找到合适的b和c（即left和right指针对应的值）。

注意几个判断：

1、排序后的数组，每次更新i后，判断元素正负，大于0可以直接结束，返回结果；

2、i的去重是和前一个比较，相等continue；

3、while循环终止条件是left == right，其余情况right在left右边；

4、sum大于0，right过大；sum小于0，left过小；

5、在sum==0并保存结果后更新left和right，同样遵循“和前一个值相比较”的原则去重。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 双指针法
        results = []  # 创建答案集合
        nums.sort()  # 先对数组进行排列，保证左边小，右边大

        for i in range(len(nums)):
            # 如果排序后的第一个就比0大，可以直接返回空集
            if nums[i] > 0:
                return results
            # i的去重
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 创建双指针
            left = i + 1
            right = len(nums) - 1
            # 双指针遍历
            while right > left:
                cur_sum = nums[i] + nums[left] + nums[right]

                if cur_sum > 0:  # 大于0，说明right大了
                    right -= 1
                elif cur_sum < 0:  # 小于0，说明left小了
                    left += 1
                else:  # 等于0，append保存当前的组合
                    results.append([nums[i], nums[left], nums[right]])
                # 更新双指针
                    # left去重
                    while right > left and nums[left] == nums[left + 1]:
                        left += 1
                    # right去重
                    while right > left and nums[right] == nums[right - 1]:
                        right -= 1
                    # 更新
                    left += 1
                    right -= 1

        return results

?字典法

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 字典法
        results = []
        nums.sort()

        for i in range(len(nums)):
            # 剪枝
            if nums[i] > 0:
                break
            # i去重
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 重点用来保存当前“需要”的数字
            seen = {}
            for j in range(i + 1, len(nums)):  # j的去重，需要找到至少2不重复的，因为需要给c流出空间
                if j > i + 2 and nums[j] == nums[j - 1] == nums[j - 2]:
                    continue
                c = -(nums[i] + nums[j])  # c = 0 - i - j
                if c in seen:
                    results.append([nums[i], nums[j], c])
                    seen.pop(c)  # 如果字典里有需要的数值，就加上然后在字典里去掉
                else:
                    seen[nums[j]] = j  # 否则保存到字典
        return results

18. 四数之和 - 力扣（LeetCode）

双指针法

可以和上面三数之和对比，可以看出来四树之和就是在其基础上增加一个变量j，通过固定i和j的方式，遍历双指针。这样就可以不断举一反三出五数、六数......之和。

需要注意j的范围和剪枝、去重操作。

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        results = []
        n = len(nums)

        for i in range(n):
            # 指定target下的剪枝需要注意判断是否都是正数，负数相加可能更小
            if target > 0 and nums[i] > target:
                break
            # 去重需要注意判断是否是大于等于1的情况
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 四个数相加在三数相加基础上引入了新的大于i的变量j，同时固定这两层循环的i和j来遍历双指针
            for j in range(i + 1, n):
                # 剪枝需要判断是否是正数
                if nums[i] + nums[j] > target and target > 0:
                    break
                # 去重逻辑和i一致
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                # 设置双指针起始位置
                left = j + 1
                right = n -1
                
                while right > left:
                    cur_sum = nums[i] + nums[j] + nums[left] + nums[right]
                    # 不相等的情况下的双指针移动
                    if cur_sum < target:
                        left += 1
                    elif cur_sum > target:
                        right -= 1
                    # 相等情况下的保存和指针更新
                    else:
                        results.append([nums[i],  nums[j], 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 results

字典实现

和上面的总结一致，字典实现其实也是在原来的基础上加上了一层，也可以举一反三进行推广。

?注意！！有很多细节：

1、判断当前得到的val是否是出现过的写法；

2、将答案按照排序格式录入ans的写法。

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        # 字典法
        # nums.sort()
        freq = {}
        # 遍历nums找出每一个数字出现的频率
        for num in nums:
            freq[num] = freq.get(num, 0) + 1
        n = len(nums)
        ans = set()
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    val = target - (nums[i] + nums[j] + nums[k])
                    # 如果val是nums中的数字
                    if val in freq:
                        # 统计当前其余三个数字是val的总数
                        cnt = (nums[i] == val) + (nums[j] == val) + (nums[k] == val)
                        if cnt < freq[val]:  # 如果总数比val的总出现次数少，认为val是成立的，相等则认为是重复出现的数字
                            ans.add(tuple(sorted([nums[i], nums[j], nums[k], val])))  # trick：利用了set不计重复元素的特性，但是必须排序再添加（必须转化为tuple格式）
        return [list(x) for x in ans]  # 迭代输出ans中的list

第7天完结🎉