代码随想录算法训练营day7|● 454.四数相加II ● 383. 赎金信 ● 15. 三数之和 ● 18待做

tristan241001 / 2024-10-07 / 原文

学习资料：https://programmercarl.com/0015.三数之和.html#其他语言版本

学习记录：
454.四数相加（hash_dict，前两个数一组遍历a+b，后两个数一组遍历找0-(a+b)）

点击查看代码

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        hash_map = dict()
        for i in nums1:
            for j in nums2:
                key=i+j
                hash_map[key]=hash_map.get(key, 0)+1
        count = 0
        for i in nums3:
            for j in nums4:
                key=0-(i+j)
                if key in hash_map:
                    count += hash_map[key]
        return count

383.赎金信（类似于有效的字母异位字，只要note里字母统计个数小于等于magzinine里的统计字母个数，则返回True）

点击查看代码

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        ran_list = [0]*26
        mag_list = [0]*26
        for i in ransomNote:
            index= ord(i)-ord('a')
            ran_list[index] += 1
        for i in magazine:
            index = ord(i)-ord('a')
            mag_list[index] += 1
        for i in range(26):
            if ran_list[i]<=mag_list[i]:
                pass
            else:
                return False
        return True

15.三数之和（不用hash表，用左右指针法，重点在于结果去重；初始数组排序；i代表a遍历全数组，left=i+1, right=nums.size-1;left和right向中间靠拢；因为要三个数所以left

点击查看代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()
        for i in range(len(nums)):
            if nums[i] > 0:
                return result
        
            # 第一次去重
            if i > 0 and nums[i] == nums[i-1]:
                continue
            # 双指针
            left = i + 1
            right = len(nums)-1
            while right > left:
                sum = nums[i]+nums[left]+nums[right]
                if sum < 0:
                    left += 1
                elif sum > 0:
                    right -= 1
                else:
                    result.append([nums[i], nums[left], nums[right]])
                    # 在收获了一个结果后，对后续结果进行去重
                    while right>left and nums[right]==nums[right-1]:
                        right -= 1
                    while right>left and nums[left]==nums[left+1]:
                        left += 1
                    left += 1
                    right -= 1
        return result

PS：18题明天再做吧，假期结束啦，今天吃土豆烧排骨、甜椒炒肉、糖醋莲白，幸福~~~