454. 四数相加 II - 力扣（LeetCode）

解题思路

两数之和之不去重plus版
因为用存两数之和出现的次数，所以要用字典；不用数组是因为int可能会很大，用数组映射不合适。

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        hashtable1 = {}
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                if nums1[i]+nums2[j] in hashtable1:
                    hashtable1[nums1[i]+nums2[j]] += 1
                else:
                    hashtable1[nums1[i]+nums2[j]] = 1

        count = 0
        for i in range(len(nums3)):
            for j in range(len(nums4)):
                if -(nums3[i]+nums4[j]) in hashtable1:
                    count += hashtable1[-(nums3[i]+nums4[j])]

        return count

• 中间的运算结果可以用中间值存放，不然看起来繁琐

383. 赎金信 - 力扣（LeetCode）

解题思路

magazine存到hashtable，ransomNote遍历，有一个对应的，magazine就-1，没找到或者找到对应的值为0，就返回False

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        hashtable = {}
        for ch in magazine:
            if ch in hashtable:
                hashtable[ch] += 1
            else:
                hashtable[ch] = 1
        
        for ch in ransomNote:
            if ch not in hashtable or hashtable[ch] == 0:
                return False
            else:
                hashtable[ch] -= 1
        return True

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

解题思路

• 双指针，排序，固定一位，然后移动左右指针；
• 去重是关键，abc都要去重。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()

        result = []

        for i in range(len(nums)):
            if nums[i] > 0:
                return result

            if i>0 and nums[i] == nums[i-1]: #如果和上一个i对应的值一样，跳过，不能是下一个
                continue

            left = i+1 #
            right = len(nums)-1

            while left < right:
                if (nums[i]+nums[left]+nums[right]) > 0:
                    right -= 1
                elif(nums[i]+nums[left]+nums[right]) < 0:
                    left += 1
                else:
                    result.append([nums[i], nums[left], nums[right]])

                    left += 1
                    right -= 1

                    while (left < right) and nums[left] == nums[left-1]:
                        left += 1 # 不能用if，不然只能去一个重复的
                    while (left < right) and nums[right] == nums[right+1]:
                        right -= 1
        return result

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

解题思路

三数之和plus版，注意去重和剪枝

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

        for k in range(len(nums)):
            if target > 0 and nums[k] > target: #一级剪枝
                break

            if k>0 and nums[k] == nums[k-1]: #一级去重
                continue
            
            for i in range(k+1, len(nums)): 
                if target > 0 and nums[k]+nums[i] > target:#二级剪枝
                    break

                if i>k+1 and nums[i] == nums[i-1]: #二级去重
                    continue

                left = i+1
                right = len(nums)-1
                
                while left < right:
                    sums = nums[k] + nums[i] + nums[left] + nums[right]
                    if sums > target:
                        right -= 1
                    elif sums < target:
                        left += 1
                    else: 
                        result.append([nums[k],nums[i],nums[left],nums[right]])
                    
                        left += 1
                        right -= 1

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

        return result