目录
链接： 454. 四数相加 II - 力扣（LeetCode）
本题的暴力法是4个for loop循环，时间复杂度为O(N^4)，不再赘述。
这道题目的一个很重要的点是不用考虑去重，例如A B C D 中的所有元素都为0的时候，就算找到的元组都是[ 0, 0, 0, 0 ]这种形式，但是他们仍然属于不同的元组，因为其中的0来自于数组中不同的位置。这大大简化了这道题的思路。
怎么想到用哈希法？
思考：在集合中判断一个元素是否出现过的时候，想到要用哈希法。
可以先遍历数组A和数组B，储存所有可能性在哈希表中，然后一一遍历数组C和数组D的组合；看0-（C+D)元素是否在哈希表中出现，如果出现，就找到了合适的元组，这里涉及到了在哈希表中判断元素是否出现过，所以想到用哈希法。
用哈希法的哪种数据结构？
数值大小不可控，不可以用array；题意要统计元组出现的次数，所以我们需要有key-value的键值对, 所以说用Map。
Map用来干啥？其中的Key-value分别是啥？
Map用来存AB数组元素相加的所有可能性，key为相加之和的数值，value为这个数值出现的次数。
具体执行思路
# Map作哈希表
# time:O(n^2); space:O(n^2)
class Solution(object):
def fourSumCount(self, nums1, nums2, nums3, nums4):
"""
:type nums1: List[int]
:type nums2: List[int]
:type nums3: List[int]
:type nums4: List[int]
:rtype: int
"""
record = {}
count = 0
for i in nums1:
for j in nums2:
Sum = i+j
if Sum in record:
record[Sum] += 1
else:
record[Sum] = 1
for k in nums3:
for l in nums4:
target = 0-k-l
if target in record:
count += record[target]
return count时间复杂度：O(n^2)
我们使用了两次二重循环，时间复杂度均为 O(n^2)；在循环中对哈希映射进行的修改以及查询操作的期望时间复杂度均为 O(1)，因此总时间复杂度为 O(n^2)；
空间复杂度：O(n^2)
即为哈希映射需要使用的空间。在最坏的情况下，A[i]+B[j]的值均不相同，因此值的个数为 n^2 ，也就需要 O(n^2) 的空间。
2. 代码随想录
本题学习时间：60分钟。
暴力方法？
首先想到的第一思路是暴力枚举了，两层for循环，不断去寻找，首先遍历magazine，再遍历ransom，如果在ransom中找到了和magazine相同的字符，则再ransom中删掉这个字符，遍历结束之后，如果ransom为空了，说明，magazine的字符可以组成ransom，这里时间复杂度是比较高的，而且里面还有一个字符串删除也就是erase的操作，也是费时的。时间复杂度为O(N^2)；空间复杂度为O(1)，暴力解法只叙述思路，不再赘述。
这道题目和LeetCode242.有效的字母异位词很像，它相当于求 字符串a 和 字符串b 是否可以相互组成 ，而这道题目是求 字符串a能否组成字符串b，而不用管字符串b 能不能组成字符串a。
如何想到用哈希法？
本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。也就是看字符串ransom中的元素，是否在magazine中出现过。
在集合中判断一个元素是否出现过，则立即想到哈希法。
哈希表用哪种数据结构？其组成元素代表什么含义？
题目中还有两点细节需要注意：
因为不可以重复使用，所以我们需要在建立哈希表的时候，统计每个元素出现的次数，因为字符串中只有小写字母，小写字母最多只有26种，所以可以用长度为26的数组来作哈希表，数组的下标索引是从“a”-”z”的各个字母，数组值是该字母出现的次数。
哈希解法实现思路
因为题目所只有小写字母，那可以采用空间换取时间的哈希策略， 用一个长度为26的数组还记录magazine里字母出现的次数。
然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。依然是数组在哈希法中的应用。
# 数组作哈希表
# time:O(m+n);space:O(1)
class Solution(object):
def canConstruct(self, ransomNote, magazine):
"""
:type ransomNote: str
:type magazine: str
:rtype: bool
"""
record = [0]*26
# 通过recode数据记录 magazine里各个字符出现次数
for element in magazine:
index = ord(element) - ord("a")
record[index] += 1
# 遍历ransomNote，在record里对应的字符个数做--操作
for item in ransomNote:
index = ord(item) - ord("a")
record[index] -= 1
for i in record:
# 如果小于零说明ransomNote里出现的字符，magazine没有
if i <0:
return False
return True
时间复杂度：O(m + n)
其中 m 是字符串 ransomNote 的长度，n 是字符串 magazine 的长度，我们只需要遍历两个字符一次即可；
空间复杂度：O(|S|) = O(1）
S 是字符集，这道题中 S 为全部小写英语字母，因此 |S| = 26。
1. 力扣
2. 代码随想录
本题学习时间：60分钟。
这道题目可以像两数之和一样使用哈希法，但是有一个巨大的难点，就是元组不可以重复，所以说需要做去重操作，而去重的操作中有超级多的细节需要注意，在面试中很难写出bug free的代码。
虽然说哈希法也是时间复杂度为O(N^2)的算法，但是双指针法会比哈希法更加高效。
if (i > 0 && nums[i] == nums[i - 1])这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。这是一个非常细节的思考过程。# time:O(N^2); space:O(logN)/O(N)
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
result = []
for i in range(len(nums)):
# 如果第一个最小的元素都大于0的话，可以直接退出for loop
if nums[i] > 0:
break
# 这里是元素i的去重，这里很细节，必须和前面的i作比较
# 否则 -1 -1 0 0 2 ，就会漏掉 -1 -1 2 这种情况
if i>0 and nums[i] == nums[i-1]:
# 退出当前这个for loop ，i+1进入下一个loop
continue
# 初始化left和right
left = i+1
right = len(nums)-1
# 这里不考虑left = right的情况，因为这种情况没有意义，
# left and right 必须是不同的两个数才行
while left<right:
# 当和偏大的时候，让right左移变小
if nums[i]+nums[left]+nums[right] >0:
right -= 1
# 当和偏小的时候，让left右移变大
elif nums[i]+nums[left]+nums[right] <0:
left += 1
else:
# 先把这个结果给加上，再考虑left和right去重的问题
result.append([nums[i],nums[left],nums[right]])
# 找到一个结果之后left和right向中间聚拢一步
left += 1
right -= 1
# 开始处理left和right的去重细节
# 这里也类似前面的i,要和之前已经处理过的数据比较
# 这里同时要保证left是小于right的，不然容易越界，也没必要做任何操作了
# 违反这个会直接退出大的while（left<right）循环
# 这里要用while处理，因为可能有连续的好几个
while left<right and nums[left] == nums[left-1]:
left += 1
while left<right and nums[right] == nums[right+1]:
right -= 1
return result时间复杂度：O(n^2)。
首先排序的时间复杂度为O(NlogN）；第一个循环，遍历元素i，在每个元素i中，两个指针left和right会把数组也遍历一遍，因此总共的遍历的复杂度是O(N^2)，加起来就是O(N^2)；
空间复杂度：O(1)/O(N)
输出答案的空间不会有很多，可以认为是O(1），排序所需要的空间复杂度也为O(1）；但如果题意不能原地排序的话，需要创建一个新的数组，那么排序的空间复杂度变为O(N）。
本题学习时间：120分钟。
四数之和，和三数之和是一个思路，都是使用双指针法, 基本解法就是在它的基础上再套一层for循环。
三数之和的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。
四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。
但是有一些细节需要注意
1. 一级剪枝操作有所变化，不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。（亲自写代码就能感受出来）