从2数和-3数和-到4数和

通解：【锁定目标对象，字典O(1)查找】

2数和

给定一个数组nums和一个target，求数组中两数和为target的两数下标，这样的两数下标可能有多组。每个数不能重复使用

思路：
最暴力的就是两层for循环，两两相加逐个判断，即两数a+b与target的大小关系。
但事实上，对于每一个数num，我们确切地知道它需要的余数是target-num
因此，在外层循环确定一个基数后，计算余数pair_num，我们只要看有没有另一个数与pair_num相等
怎么看是否有数与pair_num相等

• 法1：对于每个基数，遍历剩下的数看是否等于pair_num。这和两层for循环，两两相加逐个判断复杂度一样
• 法2：我们可以先遍历nums一次，以元素值为key，index为val构造一个字典，这样查找pair_num就是O(1) not O(n)。然后再遍历一次nums，每次检查当前元素的余数是否在字典中。总时间复杂度O(n)
• 法3：对法2进行优化，遍历nums一次，核心两步走：找前面的队友 + 登记自己等后面的人来找遍历过程中计算当前元素num的余数pair_num，在字典中查找小伙伴pair_num，若存在，结算结果（表示num可以与前面已经扫过的数配对），不存在就算了；然后把num自身加入字典等待后面的数来配对。总时间复杂度O(n)，且只需遍历一次

注意：法3的算法是自带避免重复的，因为每一次查找num的小伙伴pair_num都靠字典，而字典只记录已经扫过的数，所以【每一次都是与之前的数做配对】，避免了结果的重复
这种方法提供了一种可推广的避免重复的策略——每次只在一侧进行计算。其实，我们在解决两两握手问题时，也用了这个策略，第一个人需要和后面的人握n-1次，第二个人需要和后面的人握n-2次, ...也是只在一侧进行计算

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[List[int]]:
        # [2,2,1,3] - > {2:[0,1], 1:[2], 3:[3]}
        d = dict()
        l = len(nums)
        res = []
        for i in range(l):
            num = nums[i]
            # 计算余数
            pair_num = target - num
            # 在字典中找pair_num，找到则说明num可以与【前面扫过】的某些数配对
            if pair_num in d:
                pair_num_index = d[pair_num]
                for index in pair_num_index:
                    res.append([i,index])
                    
            # 把num自己加入字典d，等后面的小伙伴找
            if num in d:
                d[num].append(i)
            else:
                d[num] = [i]
        return res

3数和

给定一个数组nums和一个target，求数组中3数和为target的3数下标，这样的3数下标可能有多组。每个数不能重复使用

思路：
3数和 = num1 + num2 + num3 = num1 + (num2 + num3)
将num1视为一个数，(num2 + num3)视为另一个数，则转换为两数和的形式

class Solution:
    def threeSum(self, nums: List[int], target: int) -> List[List[int]]:
        
        l = len(nums)
        res = []
        for i in range(l):
            num1 = nums[i]
            pair_target = target - num1
            
            ### 在num[i]右侧的子数组中查找两数和为pair_target的两数下标
            
            # [2,2,1,3] - > {2:[0,1], 1:[2], 3:[3]}
            d = dict()
            for j in range(i+1, l):
                num2 = nums[j]
                num3 = pair_target - num2
                # 找队友
                if num3 in d:
                    for num3_index in d[num3]:
                        res.append([i, j, num3_index])
                # 登记自己
                if num2 in d:
                    d[num2].append(j)
                else:
                    d[num2] = [j]
        return res

4数和

给定一个数组nums和一个target，求数组中4数和为target的4数下标，这样的4数下标可能有多组。每个数不能重复使用

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # 思路：
        # 求出数组内的任意两数的两数和，存到新list：two_sum
        # 再对two_sum中的元素做一次两数和

        # 字典d，存放组成两数和对应的所有两数下标
        d = dict()
        # 存放所有的两数和
        two_sum = list()
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                temp_sum = nums[i] + nums[j]
                if temp_sum not in d:
                    d[temp_sum] = []
                d[temp_sum].append({i,j})
                two_sum.append(temp_sum)
        
        res = set()

        # 下面套用两数和问题的解法
        pair_d = dict()
        for i in range(len(two_sum)):
            pair = target - two_sum[i]
            # 【找队友】找余数pair是否在字典pair_d中
            if pair in pair_d:
                # 找到两数和two_sum[i]/两数和pair的所有组成可能，遍历
                for pair_index in d[two_sum[i]]:
                    for p_index in d[pair]:
                        # 如果下标没有交集，才是4个数
                        if not pair_index.intersection(p_index):
                            a = [nums[ii] for ii in pair_index]
                            b = [nums[jj] for jj in p_index]
                            # 为了方便去重，先排个序
                            four_nums = tuple(sorted(a+b))
                            res.add(four_nums)
            # 【登记自己】
            pair_d[two_sum[i]] = 1
        
        ans = [list(ele) for ele in res]
        return ans

事实上，两数【和】只是一种形式，只要数与数之间能够建立起等量关系从而能明确知道自己的‘队友’是谁，那么不管是和/积/商/差，异或是其他的关系，都可以用【找队友+登记自己】的方法来解题

练习:
leetcode#### 1010. 总持续时间可被 60 整除的歌曲
给定一个数组nums，求所有这样的【两个数】，使它们的和能被60整除

思路：利用(a + b) % 60 = (a % 60 + b % 60) % 60，将a % 60 和 b % 60看成2个数moda modb，if (moda + modb) % 60 == 0，则有等量关系【modb = (60 - moda) % 60】，用这个关系找队友

# 两数和翻版

class Solution:
    # def numPairsDivisibleBy60(self, time: List[int]) -> int:
    #     # (a + b) % 60 = (a % 60 + b % 60) % 60
    #     res = 0
    #     l = len(time)
    #     index_d = dict()
    #     for i in range(l):
    #         mod = time[i] % 60
    #         pair = (60 - mod) % 60
    #         # 找队友
    #         if pair in index_d:
    #             res += len(index_d[pair])
            
    #         # 登记自己
    #         if mod in index_d:
    #             index_d[mod].append(i)
    #         else:
    #             index_d[mod] = [i]
    #     return res

    # 使用bitmap来代替字典
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        # 使用bitmap
        d = [0] * 60
        res = 0
        # 每次只与已经扫过的元素做匹配计算
        for t in time:
            t = t % 60
            # res += d[-t] or res += d[(60-t) % 60]
            res += d[(60-t) % 60]
            d[t] += 1
        return res

leetcode#### 15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组

分析：由于本题求的不是下标而是元素本身，且不能重复，因此我们无需关注下标到底是多少，字典的任务就是记住余数出现过没有。下面给出字典法，同时给出双指针法

# class Solution:
#     def threeSum(self, nums: List[int]) -> List[List[int]]:
#         # 排序+双指针
#         # 先将数组nums排序，排序后可以基于数组的有序性，使用双指针法在O(N)时间复杂度内求得剩下两个数
#         nums.sort()
#         res = set()
#         l = len(nums)
#         for i in range(l):
#             if i == 0 or nums[i] > nums[i-1]:
#                 # i指向首个数
#                 first_num = nums[i]
#                 target = -1 * first_num
#                 left = i + 1
#                 right = l - 1
#                 # left和right指向剩下两个数
#                 while left < right:
#                     temp = nums[left] + nums[right]
#                     if temp < target:
#                         left += 1
#                     elif temp > target:
#                         right -= 1
#                     else:
#                         res.add((first_num, nums[left], nums[right]))
#                         left += 1
#                         right -= 1
#         res = [list(ele) for ele in res]
#         return res

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 不排序的，使用字典的解法。
        # 本解法将nums[i]作为first_num，使用字典法查找后面的2数和。由于题目要求不能出现重复三元组，因此将满足题意的3元组sort以方便去重
        res = set()
        l = len(nums)
        for i in range(l):
            first_num = nums[i]
            target = -1 * first_num
            d = dict()
            for j in range(i+1, l):
                sec_num = nums[j]
                # 如果第三个数已经在字典中，结算
                if target - sec_num in d:
                    temp_res = [first_num, sec_num, target - sec_num]
                    temp_res.sort()
                    res.add(tuple(temp_res))
                d[sec_num] = j
        res = [list(ele) for ele in res]
        return res

336. 回文对

给定一组 互不相同 的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

常规思路，words[i] + words[j]能不能回文，先拼起来再回文检查，时间复杂度O(avg_len * n^2)，avg_len指word的平均长度

更快的方法是，我们不要像常规思路一样无脑试每一种可能，对于一个给定的word，去求出能够和word形成回文串的字符有哪些，然后再去words里面找，才是正道

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        l = len(words)
        res = []
        d = dict()
        # 字典登记
        for i in range(l):
            d[words[i]] = i
        for i in range(l):
            w = words[i]
            for j in range(len(w)+1):
                prefix, endfix = w[:j], w[j:]
                # 如果前缀回文
                if self.isPalindrome(prefix):
                    if endfix[::-1] in d:
                        index = d[endfix[::-1]]
                        if index != i:
                            res.append([index, i])
                # 如果后缀回文，且后缀不为空【因为前缀为空和后缀为空的目标pair是一致的，在前缀那计算一次就可以了】
                if j != len(w) and self.isPalindrome(endfix):
                    if prefix[::-1] in d:
                        index = d[prefix[::-1]]
                        if index != i:
                            res.append([i, index])
                                
        return res

    def isPalindrome(self, s) -> bool:
        l = len(s)
        if l == 0:
            return True
        else:
            left, right = 0, l-1
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True