代码随想录算法训练营Day7 | LeetCode454 四数相加II、LeetCode383 赎金信、LeetCode15 三数之和、LeetCode18 四数之和 - 慕念

LeetCode454 四数相加II

题目链接/文章讲解/视频讲解：https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html

⭐合并，整体时间复杂度$O(n^2)$

本题解题步骤：

首先定义一个dict，key放a和b两数之和，value 放a和b两数之和出现的次数。
遍历大A和大B数组，统计两个数组元素之和和出现的次数，放到map1中。
同理遍历大C和大D数组，统计两个数组元素之和和出现的次数，放到map2中。
定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
遍历map1和map2，当key1 + key2 = 0时，count += value1 * value2

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
        """

        dict1 = {}
        for i in nums1:
            for j in nums2:
                if i + j in dict1:   # 已存在
                    
                    dict1[i + j] += 1
                else:   # 初始化
                    
                    dict1[i + j] = 1
        
        dict2 = {}
        for i in nums3:
            for j in nums4:
                if i + j in dict2:
                    dict2[i + j] += 1
                else:  
                    dict2[i + j] = 1
        
        count = 0
        for key1,value1 in dict1.items():
            for key2,value2 in dict2.items():
                if key1 + key2 == 0:
                    count += value1 * value2
        return count

按照代码随想录的思路，后半部分不一样：

class Solution(object):
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        # 使用字典存储nums1和nums2中的元素及其和
        
        hashmap = dict()
        for n1 in nums1:
            for n2 in nums2:
                if n1 + n2 in hashmap:
                    hashmap[n1+n2] += 1
                else:
                    hashmap[n1+n2] = 1
        
        # 如果 -(n1+n2) 存在于nums3和nums4, 存入结果
        
        count = 0
        for n3 in nums3:
            for n4 in nums4:
                key = - n3 - n4
                if key in hashmap:
                    count += hashmap[key]
        return count

LeetCode383 赎金信

题目链接/文章讲解：https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html

做过LeetCode242 有效的字母异位词之后再做这道就比较容易了，注意python中ord()函数返回字符ASCII数值

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        letter = [0] * 26

        for i in magazine:
            letter[ord(i) - ord('a')] += 1
        for i in ransomNote:
            letter[ord(i) - ord('a')] -= 1
        
        for i in letter:
            if i < 0:
                return False
        return True

LeetCode15 三数之和

题目链接/文章讲解/视频讲解：https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html

⭐用hash复杂，相比起两数之和又多了去重的要求

⭐选用双指针法（先排序）时间复杂度：$O(n^2)$。

⭐for循环中i遍历确定a的值，再定义left和right两个指针，left指向b的取值，right指向c的取值，即 a = nums[i]，b = nums[left]，c = nums[right]

如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

15.三数之和

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort() # 排序没有返回值
        
        res = []

        for i in range(len(nums)):
            left = i + 1
            right = len(nums) - 1
            while right > left:
                if nums[i] + nums[left] + nums[right] > 0:
                    right -= 1
                elif nums[i] + nums[left] + nums[right] < 0:
                    left += 1
                else:   # 相加为0，记录
                    
                    res.append([nums[i], nums[left], nums[right]])
                    right -= 1
                    left += 1
        # 去重
        
        s = []
        for i in res :
            if i not in s :
                s.append(i)
        return s

对比代码，优化改进：

排序之后如果第一个元素已经大于零，那么不可能凑成三元组

for i in range(len(nums)):
    # 排序之后如果第一个元素已经大于零，那么不可能凑成三元组
        
    if nums[i] > 0:
        break

跳过相同的元素以避免重复

if i > 0 and nums[i] == nums[i - 1]:
    continue

# 当sum=0时，加入res后，跳过相同的元素以避免重复
    
while right > left and nums[right] == nums[right - 1]:
    right -= 1
while right > left and nums[left] == nums[left + 1]:
    left += 1

LeetCode18 四数之和

题目链接/文章讲解/视频讲解：https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html https://programmercarl.com/0001.两数之和.html)

在三数之和的基础上再套一层循环：

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

        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                left = j + 1
                right = len(nums) - 1

                while right > left:
                    _sum = nums[i] + nums[j] + nums[left] + nums[right]
                    if _sum > target:
                        right -= 1
                    elif _sum < target:
                        left += 1
                    else:   # 相加为target，记录
                        
                        res.append([nums[i], nums[j], nums[left], nums[right]])
                        right -= 1
                        left += 1
        # 去重
        
        s = []
        for i in res :
            if i not in s :
                s.append(i)
        return s

可以优化的地方：

不要判断nums[k] > target 就返回了，三数之和可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

当sum == target时可以继续剪枝：

while left < right and nums[left] == nums[left+1]:
    left += 1
while left < right and nums[right] == nums[right-1]:
    right -= 1

代码随想录算法训练营Day7 | LeetCode454 四数相加II、LeetCode383 赎金信、LeetCode15 三数之和、LeetCode18 四数之和

LeetCode454 四数相加II

LeetCode383 赎金信

LeetCode15 三数之和

LeetCode18 四数之和

CATALOG

FEATURED TAGS