四数相加II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

例如:
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
解释:
两个元组如下:
(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

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

这道题就是将四个数分成两组前两个数一组，并把他们的和作为key，出现的次数作为value，存到一个哈希表中。
然后遍历后两个数的组合，判断0-(i+j)是否在哈希表中，如果在，就把出现的次数加到count中（注意加的是value的值不是一，原因是不用去重）。

赎金信

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

例如:
输入: ransomNote = “a”, magazine = “b”
输出: false
输入: ransomNote = “aa”, magazine = “ab”
输出: false
输入: ransomNote = “aa”, magazine = “aab”
输出: true

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

这道题就是用一个哈希表来记录 magazine 中的字符出现的次数，然后遍历 ransomNote 中的字符，判断是否在哈希表中，如果在，就把哈希表中对应的值减一。
直到遇到了0，就说明 magazine 中的字符不能构成 ransomNote 中的字符，返回 False。跟昨天第一题很像

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

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 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]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and right < len(nums)-1 and nums[right] == nums[right - 1]:
                        right -= 1
                    right -= 1
                    left += 1
        return result

用了双指针的思路
首先先对数组排序，然后for循环用i作为第一个数，left作为第二个数，right作为第三个数，三个数求和判断是否等于0，如果等于0，就把这三个数加入到结果中。
如果大于0，就把right减一，如果小于0，就把left加一。
直到left大于等于right，就说明这个数组合完了，就可以继续下一个数了。
注意点去重操作是i和i-1比较，left和left+1比较，right和right-1比较，为啥这样的，因为i是基准，如果i和i+1判断，把下一个i跳了，i就像边界一样，left就指不到被跳的i的那个位置了，比如-2 -1 -1 0 2，但是i继续加一以后，发现和之前的i一样，这个i就可去掉了，这里不会重复是上一组的i已经用过这个顺序了，例如-1 -1 0 0 1 2，然后left和right就是和自己的下一个数比较即可，而且不会遗漏，哪怕有连续的left挑掉，right也会移动过去，不像i是基准

四数之和

题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。

示例：给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        result = []
        nums.sort()
        for i in range(len(nums)):
            if nums[i]>0 and nums[i] > target//4 :
                break #这里不能return result
            if i>0 and nums[i] == nums[i-1]:
                continue
            for j in range(i+1,len(nums)):
                if nums[i] + nums[j] > target and target > 0: 
                    break
                if j > i+1 and nums[j] == nums[j-1]:
                    continue
                left,right = j+1,len(nums)-1
                while left < right:
                    sum_=nums[i]+nums[j]+nums[left]+nums[right]
                    if sum_ == target:
                        result.append([nums[i],nums[j],nums[left],nums[right]])
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        while right > left and nums[right] == nums[right-1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif sum_ > target    :
                        right -= 1
                    else :
                        left += 1
        return result