从2数和-3数和-到4数和 2020-05-09（未经允许，禁止
从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
