# 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

3. 复杂度分析

时间复杂度：O(n^2)

我们使用了两次二重循环，时间复杂度均为 O(n^2)；在循环中对哈希映射进行的修改以及查询操作的期望时间复杂度均为 O(1)，因此总时间复杂度为 O(n^2)；

空间复杂度：O(n^2)

即为哈希映射需要使用的空间。在最坏的情况下，A[i]+B[j]的值均不相同，因此值的个数为 n^2 ，也就需要 O(n^2) 的空间。

4. 思考

提出疑问，为什么不只遍历A，得到Map，然后再遍历B，C，D中所有组合的可能性？因为这样的话，时间复杂度和空间复杂度就提升为O(N^3)；
注意count计数器在加的时候，并不是直觉上的count+= 1，因为出现的频率不一定是1，比如说map中储存的是5:3，对应三组AB元组，分别是，A[1] +B[2] = 5，A[2] +B[3] = 5，A[3] +B[4] = 5，然后在C+D中找到了一对相加等于-5的，所以说这样就找到了三组四元组，应该count+3；
和其他题目的比较思考：这道题和两数之和思路非常一致，只是创建Map和查找Map的时候，都变成了两个for loop一起遍历，value存的是下标；和有效字母的异位词处理也很类似，只是根据不同情况用到的元素不同，都是先创建容器，再利用容器找我们需要的结果；
题目乍眼看和三数之和，四数之和差不多，其实差很多；本题是使用哈希法的经典题目，而以上两道题不适合使用哈希法，因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，很有多细节需要处理。而这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于题目18. 四数之和，题目15.三数之和，还是简单了不少！

Reference

1. 力扣

2.??代码随想录

本题学习时间：60分钟。

?Leetcode383. 赎金信?

链接：赎金信 - 赎金信 - 力扣（LeetCode）

1. 思路

暴力方法？

首先想到的第一思路是暴力枚举了，两层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所需要的所有字母。依然是数组在哈希法中的应用。

2. 代码实现

# 数组作哈希表
# 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

3. 复杂度分析

时间复杂度：O(m + n)

其中 m 是字符串 ransomNote 的长度，n 是字符串 magazine 的长度，我们只需要遍历两个字符一次即可；

空间复杂度：O(|S|) = O(1）

S 是字符集，这道题中 S 为全部小写英语字母，因此 |S| = 26。

4. 思考

可以直接用Map吗？其实在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。所以数组更加简单直接有效！
本题和 242.有效的字母异位词是一个思路，算是拓展题；
本题是使用array 巧妙解决的问题，好好体会一下哈希法如何提高程序执行效率，降低时间复杂度，当然使用哈希法会提高空间复杂度，但一般来说我们都是舍空间换时间，工业开发也是这样。

Reference：

1.?力扣

2.??代码随想录

本题学习时间：60分钟。?

Leetcode15. 三数之和

链接：?15. 三数之和 - 力扣（LeetCode）

方法一：双指针法

1. 思路

这道题目可以像两数之和一样使用哈希法，但是有一个巨大的难点，就是元组不可以重复，所以说需要做去重操作，而去重的操作中有超级多的细节需要注意，在面试中很难写出bug free的代码。

虽然说哈希法也是时间复杂度为O(N^2)的算法，但是双指针法会比哈希法更加高效。

拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。
处理一下边界的逻辑，如果nums[i]已经大于0，那么不可能凑成三数和为0，直接结束这个for循环。
i元素的去重逻辑，应该是从第二个元素开始，如果和前面的元素一样的话，就直接略过当前的循环，进入下一个循环中。但这里很细节，如果写成，if（nums[i] == nums[i+1] )这种情况的话，当数组为【-1，-1,0,0,2】这样子的时候，i = 0, nums[i] = -1; left = 1; right=4; 这种情况i比较后面数，就会自动i+ 1= 1开始考虑这个循环，会忽略掉-1 -1 2 这种情况。所以说i=0 不比较，从i=1开始，和前面的比较，如果相同，则跳过，这才是正确的i去重的办法，**我们要做的是不能有重复的三元组，但三元组内的元素是可以重复的！**所以这里是有两个重复的维度。那么应该这么写：if (i > 0 && nums[i] == nums[i - 1])这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到结果集里。这是一个非常细节的思考过程。
依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i] b = nums[left] c = nums[right]。
接下来如何移动left 和right呢，循环条件也应该是while（left<right)，因为如果两者相等，那相当于只有两个数了，不符合题意；
如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
这个过程中，会找到三数之和等于0 的时刻，这时候，要先把它们加到result 里面去记录上，然后，在进行left和right的去重环节，这时候是拿下一个和现在的这个相比较，因为这个是已经加进去了，所以不会遗漏。

?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

3. 复杂度分析

时间复杂度：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）。

4. 思考

本题的双指针逻辑相对还比较清晰明了，但是去重的过程有很多容易出错的地方和细节；
既然三数之和可以使用双指针法，我们之前讲过的两数之和可不可以使用双指针法呢？两数之和就不能使用双指针法，因为两数之和要求返回的是索引下标，而双指针法一定要排序，一旦排序之后原数组的索引就被改变了，如果要求返回的是数值的话，就可以使用双指针法了。

本题学习时间：120分钟。

Leetcode18. 四数之和?

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

1. 思路

四数之和，和三数之和是一个思路，都是使用双指针法, 基本解法就是在它的基础上再套一层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是任意值。（亲自写代码就能感受出来）

💡 举个例子，如果nums = [ -4，-1,0,0]，target=-5， nums[k]=-4>-5;按照原来的条件就直接跳过了，但是这个四元组是满足条件的，因为数组中可能有负数，target也可能为负数，两个负数相加是会变小的，也是可以做剪枝操作的，只是要再加上一个条件，即target>0, 这样nums[k]就也大于0。

2. 同样的道理也可以用在二级剪枝上，将nums[k]+ nums[i] 看作整体，剪枝条件是nums[k]+ nums[i]>target>0。

2. 代码实现

# 双指针法
# time:O(N^3);space:O(1)/O(N)
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        result = []
        length = len(nums)
        for k in range(length):
            # 一级剪枝
            if nums[k]>target and target>0:
                break
            # 一级去重
            if k >=1 and nums[k] == nums[k-1]:
                continue
            for i in range(k+1,length):
                # 二级剪枝
                if nums[k]+nums[i] > target and target>0:
                    break
                # 二级去重
                if i>=k+2 and nums[i] == nums[i-1]:
                    continue
                # 初始化双指针
                left = i+1
                right = length-1
                while left<right:
                    # 双指针逻辑处理
                    if nums[k]+nums[i]+nums[left]+nums[right] > target:
                        right -= 1
                    elif nums[k]+nums[i]+nums[left]+nums[right] < target:
                        left += 1
                    else:
                        result.append([nums[k],nums[i],nums[left],nums[right]])
                        left += 1
                        right -= 1
                        # left和right的去重操作
                        while left<right and nums[left] == nums[left-1]:
                            left += 1
                        while left<right and nums[right] == nums[right+1]:
                            right -= 1
        return result

3. 复杂度分析

时间复杂度：O(n^3) 其中 n是数组的长度。排序的时间复杂度是 O(n log n)，枚举四元组的时间复杂度是 O(n^3)，因此总时间复杂度为 O(n^3+n\log n)=O(n^3)

空间复杂度：O(1)/O(N)

其中 n是数组的长度。空间复杂度主要取决于排序是否额外使用空间。如果允许原地排序，则为O(1），不允许则为O(N)；输出的答案考虑为O（1）级别。

4. 思考

在三数之和中，双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。那么一样的道理，五数之和、六数之和等等都采用这种解法；
之前我们讲过哈希表的经典题目，四数相加，相对于本题简单很多，因为本题是要求在一个集合中找出四个数相加等于target，同时四元组不能重复；而四数相加是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于本题还是简单了不少！
双指针法的总结：

双指针法将时间复杂度：O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级，题目如下：
链表相关双指针题目：
双指针法在字符串题目中还有很多应用，后面还会介绍到。