Day07_哈希表

6. 四数相加 II

454. 四数相加 II
思路：

首先观察数据范围-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228,说明四个数相加不会爆int
1 <= n <= 200，说明如果纯暴力四层循环会超过1s， $O(n^4)$
考虑到前面做的题，将一个数组中的数据全部放到集合里，利用另一个数组中的元素去集合里判断。

将四个长度为n的数组组合成两个长度为n^2的数组
然后将一个数组放入哈希表，遍历另一个数组判断其相反数是否在哈希表中。不使用集合是因为这里可能出现num1[i] + num2[j] == nums1[k] + nums2[l]的情况，使用集合的话就会使答案统计不全。

时间复杂度为 $O(n^2)$

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> my_map;
        int count = 0;
        for (int a : nums1) {
            for (int b : nums2) {
                my_map[a + b]++; // 将数组1，2合并，并建立哈希表
            }
        }
        for (int c : nums3) {
            for (int d : nums4) {
                count += my_map[-c-d]; // 将数组3，4合并，并在哈希表中找其相反数
            }
        }
        return count;
    }
};

7. 赎金信

383. 赎金信
思路：

只要ransomeNote中的字母字magezine中全都出现过，并且magezine中对应字母的数量也够即可。
由于只有26个小写字母，可以直接映射到数字下标0~25中建立哈希表。

利用magezine中的字母建立哈希表
遍历ransmoeNote中的字母，每遍历一个就消耗一个哈希表中的字母，如果哈希表中的字母不够用，则返回false；够用就返回true。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int my_map[26] = {0};
        for (char mage : magazine) {
            my_map[mage - 'a']++;
        }
        for (char ran : ransomNote) {
            if (my_map[ran - 'a'] <= 0) return false;
            my_map[ran - 'a']--;
        }
        return true;
    }
};

8. 三数之和

15. 三数之和

数据范围：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105

思路：

根据数据范围判断，三数之和不会爆int，但是如果纯暴力三层循环的话会超时, $O(n^3)$ 。
太菜了，经过一波思考，唯一能想到的就是看能不能通过排个序，整个正负数划分之类的，但是想不明白。
看题解！
利用双指针，固定一个指针i用来遍历整个数组，在区间(i, nums_size - 1]内建立两个指针，left在区间最左端向右动，right在区间最右端向左动，如此寻找目标三元组可做到不重不漏。
上述方法的复杂度为 $O(n^2)$
需要考虑三个指针位置的去重问题，代码如下

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int nums_size = nums.size();
        sort(nums.begin(), nums.end()); // 升序排列
        for (int i = 0; i < nums_size; ++i) {
            if (nums[i] > 0) return ans; // 第一个数最小，如果此数大于0，三数之和不可能为0
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 第一个数去重
            int left = i + 1;
            int right = nums_size - 1;
            while (left < right) { // nums[left] 和 nums[right]可以相同，但是下标不能相同
                if (nums[i] + nums[left] + nums[right] < 0) left++; // 三数之和小了，固定位置i和right不动，left右移
                else if (nums[i] + nums[left] + nums[right] > 0) right--; // 三数之和大了，固定位置i和left不动，right左移
                else {
                    ans.push_back(vector<int> {nums[i], nums[left], nums[right]});
                    /*
                        如果出现左边两个数相同的结果，已经加入ans了，不能出现第二次
                        left 与 left+1 比较，
                        并在最后添加一个left++,移动到第一个不相同的数字位置
                    */
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    /*  对于right，相同的值没有意义，因为之前已经得到了该值的所有答案组合
                        不和 right+1 比较是避免第一次判断越界，所以和 right-1 比较，
                        并在最后添加一个 right--,将right指针移动到第一个没有出现过的值上
                    */
                    while (left < right && nums[right] == nums[right - 1]) right--; 
                    left++;
                    right--;
                }
            }
        }
        return ans;
    }
};

9. 四数之和

18. 四数之和
思路：

和三数之和一个思路，还是双指针，只不过把固定的指针从一个i变成了一个i和j的排列组合。然后在区间[j+1, nums_size-1]内用双指针遍历。

提交的时候记得把cout注释掉，不然显示超时了，自己debug半天还不知道咋回事

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int nums_size = nums.size();
        for (int i = 0; i < nums_size - 1; ++i) {
            if (nums[i] > target && nums[i] > 0) break; // 一级剪枝
            if (i > 0 && nums[i] == nums[i - 1]) continue; // nums[i]去重
            for (int j = i + 1; j < nums_size; ++j) {
                long static_num = nums[i] + nums[j];
                if (static_num > target && static_num > 0) break; // 二级剪枝
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // nums[j]去重
                int left = j + 1;
                int right = nums_size - 1;
                while (left < right) {
                    // cout << static_num << " " << i << " " << j << " " << left << " " << right << endl;
                    if (static_num + nums[left] + nums[right] < target) left++;
                    else if (static_num + nums[left] + nums[right] > target) right--;
                    else {
                        ans.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    }
                }
            }
        }
        return ans;
    }
};