代码随想录7——哈希表：454四数相加II、383赎金信、15三数之和、18四数之和

1.454四数相加II 二刷无思路

参考：代码随想录，454四数相加II；力扣454: medium

二刷总结：二刷的时候一下子卡住了没了思路，其实这道题和两数之和是一样的，只不过把四数之和分解成了两数之和，只需要先统计两数之和放到哈希表中，然后再遍历另外两个数字的和，然后在哈希表中寻找有没有其对应的相反数，如果有则就找到了一组符合条件的解。

1.1.题目

1.2.解答

这道题目乍一看也是没有什么思路，直接解题步骤吧：

看上面的解题步骤，实际上就是把四数之和又分解成了两数之和，也就是day 06做的两数之和。也就是说先把A、B两个大数组中的元素进行求和累加，看他们有可能求和出现哪些值，然后作为键存到unordered_map中，值就存储A+B出现这个元素的次数。然后遍历C、D两个数组，直接算0 - (C+D)的结果在之前的map中是否出现过，如果出现过，那么至少是有一个元组能满足四数之和=0的。

另外看代码的话还有一个注意事项，就是在代码中遍历C、D两个数组的时候，找到了满足的map中的键，那么就把总次数加上该键出现的次数，C、D出现同样的键是没影响的，实际上就要把C、C出现同样的键的结果都考虑进去，才是最终的答案：

class Solution
{
public:
    int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3, vector<int> &nums4)
    {
        unordered_map<int, int> record;
        int result = 0;

        // 先求A+B，所有可能的结果存到map中
        for(auto& a : nums1)
        {
            for(auto & b : nums2)
            {
                int num = a + b;
                record[num]++;
            }
        }
        // 再求0-(c+d)，结果如果在A+B的map中，则找到符合条件的元组
        for(auto& c : nums3)
        {
            for(auto& d : nums4)
            {
                if(record.find(-c-d) != record.end())
                {
                    // 注意这里直接 += 是对的，事实是有多个c+d满足要求，
                    // 比如 A+B = 2，C+D=-2，如果有3个A+B=2的组合，有2个C+D=-2的组合
                    // 那么最后元组的个数就是3*2=6，而不是单独的一个3
                    result += record[-c-d];
                }
            }
        }

        return result;
    }
};

2.383赎金信 二刷通过

参考：代码随想录383. 赎金信；力扣383: easy

二刷总结：这道题很简单，和之前做的题是一样的，直接统计各个字符出现的次数即可。

2.1.题目

2.2.解答

这道题非常简单，和前面做的有效字母的异位词是一样的思路，都是用数组作为哈希表计算一个字符串中各个字符出现的次数，然后再遍历另一个字符串，把他出现的次数记下来，然后比较二者的字符出现次数，要保证题目的要求。

class Solution
{
public:
    bool canConstruct(string ransomNote, string magazine)
    {
        int map[26] = {0};
        for(auto& s : magazine)
            map[s - 'a']++;
        for(auto& s : ransomNote)
            map[s - 'a']--;
        for(auto& m : map)
            if(m < 0)
                return false;
        return true;
    }
};

3.15三数之和 二刷无思路

参考：代码随想录15三数之和；力扣15: medium

二刷总结：这道题二刷的时候没有思路，然后看后面的解答发现其实比较复杂，一个是使用双指针算法和前面的都不一样，另外一个是去重操作其实比较复杂。这道题目直接记住吧。

3.1.题目

3.2.解答

这道题感觉还是挺难的，看了双指针的解析之后，又理解了很久才完全搞明白。

首先先来看双指针法的解题思路：

• 对数组从小到大排序，注意数组中可能会有重复元素，因此可能会出现[-2, -1, -1, 0, 1, 2, 3]这种情况；
• 用一个索引i遍历整个数组，i所在的位置就是最终寻找的a；然后用一个left指针从i右边开始，right指针从数组末尾开始，移动left和right指针，寻找剩下所有可能的b/c。即判断a+b+c>0，则right左移；若果a+b+c<=0，则left右移；如果a+b+c=0，则找到目标值。

上面的解题思路没有问题，但是还有一个关键的问题是去重，也就是最后返回的三元组中不能有相同的。因此注意的地方：

• 根据上面寻找的方式，确定了元素a之后（即nums[i]），left/right两个指针会遍历它后面所有可能的b/c。又由于数组已经经过排序了，所以最后三元组中a的位置一定不能有重复的。比如[-4, -1, -1, 0, 1, 2]，当a是第一个-1的时候，left/right指针会遍历后面的[-1, 0, 1, 2]，从中寻找可能的b+c=1的所有组合，因此会找出来-1, 2和0, 1两个b,c的组合，这样就全都找出来了。所以最后的结果中[-1, -1, 2]和[-1, 0, 1]，其中的第一个-1都是[-4, -1, -1, 0, 1, 2]中的第一个-1。所以说元素a要保证唯一性，这个就很简单了，因为数组是排序过的，所以a的数值肯定是单调不减的，我们只要记录上一次a出现的值，保证这次查找的a的值和上次的值不一样就可以 。
• 在保证了元素a没有重复之后，另一个去重的问题就是在同一个a的情况下，元素b, c也不能有重复。其实这里跟元素a的去重就一样了，因为数组是经过排序的，遍历b的时候，它也是单调不减的，也只需要把上一次b的值记录下来，这一次b的值不等于上一次b的值，就可以保证没有重复。而保证了b的唯一性之后，由于a的唯一性早就事先保证了，因此c的唯一性自然就被a+b+c=0约束住了，就不用再考虑c的唯一性了。

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        int last_a = INT32_MAX;
        vector<vector<int>> result;

        for(int i = 0; i < nums.size(); i++)
        {
            int a = nums[i];
            // 先判断一下，因为可能遍历到某个i的位置，此时a>0，肯定不能组成三元组了，就可以提前结束了
            if(a > 0)
                return result;

            // 保证a的唯一性
            if(a == last_a)
                continue;

            // 执行到这里说明a是唯一的，更新上一次a的值
            last_a = a;   
            int left = i + 1;
            int right = nums.size() - 1;
            int last_b = INT32_MAX;    // 记录上次的b的值，保证唯一性
            while(left < right)
            {
                if((a + nums[left] + nums[right]) == 0) 
                {
                    // b的值没重复，则这次结果可以保存
                    if(nums[left] != last_b)
                    {
                        result.push_back(vector<int>{a, nums[left], nums[right]});
                        last_b = nums[left];   // 更新上次的b值
                    }
                    // 找到a+b+c=0，不管是否有重复，都要把双指针进行收缩
                    left++;
                    right--;
                }
                else if ((a + nums[left] + nums[right]) > 0)
                    right--;
                else
                    left++;
            }   
        }

        return result;
    }
};

注意：注意思考什么时候能用双指针法代替哈希法求解？上面双指针法一个很重要的条件是先对数组进行排序，然后双指针才能左右移动。因为本题只要求返回三元组的元素值，而没有要求返回索引值，所以是可以排序的。但是如果要是返回索引值，那么就不能用双指针法了，因为事先对数组进行排序会打乱数组的索引。

4.18四数之和二刷无思路

参考：代码随想录18四数之和；力扣18: medium

4.1.题目

4.2.解答

这个和三数之和的思路一模一样，只不过是再多加一个for循环。但是仍然有几点需要注意：

• 剪枝操作时候，由于target是一个数，不一定>=0，所以不能再像三数之和等于0那样，判断了a>target就直接返回，比如nums = [-4, -3, -2, -1], target = -10，a = -4的时候还是有解的，因为在nums[i]<0之前越往后加越小。所以这里判断要把num[i]>0加上
• 遍历b的时候，判断剪枝操作不能直接return，而是只能跳出当前的循环。因为可能a很小，b很大了，但是只能说明这次b太大了后面的不用遍历了。但是下次遍历的a还是很小，然后b也从很小开始遍历，仍然是有解的，所以这里不能直接return
• 求a+b+c+d的和的时候，为了防止溢出，要先把a转成long，然后相加的时候其他的几个数就默认隐式转换成long了，而不能把a+b+c+d的最后结果转成long，那样相当于还是用int相加，还是会溢出。

class Solution
{
public:
    vector<vector<int>> fourSum(vector<int> &nums, int target)
    {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        int last_a = INT32_MAX;
        // 遍历a
        for(int i = 0; i < nums.size(); i++)
        {
            int last_b = INT32_MAX;
            int a = nums[i];
            // 首先这里剪枝处理存在问题，因为此时的target不是0，如果它是负数，这么判断就有问题
            // 比如nums = [-4, -3, -2, -1], target=10, a=-4 > -10，但是往后加是存在答案的，不能跳过
            // if(a > target)
            //     return result;

            // 但是仍然可以进行一些剪枝处理，比如如果a>0，说明已经到了正数这边，那么不管target是正是负，都可跳过了
            if(a > target && a > 0)
                // return result;
                break;
            if(a == last_a)
                continue;
            last_a = a;   // 运行到这里说明a没有重复，更新last_a
            
            // 遍历b
            for(int j = i+1; j < nums.size(); j++)
            {
                int b = nums[j];
                // 提前结束，这里同理也要判断(a+b)>0
                if((a+b) > target && (a+b)>0)
                    // 注意这里不能return, 因为可能a很小，b很大了，但是只能说明这次b太大了后面的不用遍历了
                    // 但是下次遍历的a还是很小，然后b也从很小开始遍历，仍然是有解的，所以这里不能直接return
                    // return result;
                    break;
                if(b == last_b)
                    continue;
                last_b = b;    // 运行到这里说明b没有重复，更新last_b
                
                int left = j + 1; 
                int right = nums.size() - 1;
                int last_c = INT32_MAX;
                while(left < right)
                {
                    // 注意这里四个数相加，防止溢出，要先把a单独强制转成long，然后后面的和它加的时候
                    // 就会自动的进行隐式类型转换，变成long
                    if(((long)a + b + nums[left] + nums[right]) == target)
                    {
                        if(nums[left] != last_c)
                        {
                            result.push_back(vector<int>{a, b, nums[left], nums[right]});
                            last_c = nums[left];
                        }
                        // 只要找到了正确答案，不管有没有重复，都要收缩双指针
                        left++;   
                        right--;
                    }
                    else if(((long)a + b + nums[left] + nums[right]) > target)
                        right--;
                    else
                        left++;
                }
            }
        }

        return result;
    }
};

5.二刷总结一个数组内求和的方法

上面的题目中，15三数之和和18四数之和的方法都是一样的，因为他们都是在同一个数组中寻找满足条件的组合，并且存在重复组合的问题。所以解法都是使用双指针遍历最后的两个加数，然后剩下几个加数就用几层for循环。去重的问题通过备份上一次的数来实现。