C++刷题 -- 哈希表

C++刷题 – 哈希表

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法;

1.两数之和

https://leetcode.cn/problems/two-sum/
一种方法是直接两个for循环暴力求解，时间复杂度为O(N^2)；

另一种解法：使用map记录遍历过的元素

• 每次遍历一个元素，计算其与target的差值，从map中寻找差值，若存在，则返回下标，若不存在，则将遍历完的元素插入map；

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> nums_map; //记录遍历过的元素
        vector<int> res;

        for(int i = 0; i < nums.size(); i++)
        {
            int diff = target - nums[i];
            if(nums_map.find(diff) != nums_map.end()) // 差值>0且已经遍历
            {
                res.push_back(i);
                res.push_back(nums_map[diff]);
                break;
            }
            else
            {
                // diff不在map中，将遍历过的元素插入map
                nums_map.insert(make_pair(nums[i], i));
            }
        }
        return res;
    }
};

2.四数相加II

https://leetcode.cn/problems/4sum-ii/

• 将四个数组分为两组，计算出所有nums1和nums2中每个元素的和，使用map保存结果和个数；
• 然后再遍历nums3和nums4中的元素，计算0 - nums3[i] - nums4[j]的值，结果在map中寻找，如果找到，就在结果中增加相应的个数；

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> sum_map;
        int count = 0;
        for(const auto& n1 : nums1) // 保存nums1和nums2中所有对应元素的和与个数
        {
            for(const auto& n2 : nums2)
            {
                sum_map[n1 + n2]++;
            }
        }

        for(const auto& n3 : nums3) // 遍历nums3和nums4，差值在map中寻找
        {
            for(const auto& n4 : nums4)
            {
                int diff = 0 - n3 - n4;
                if(sum_map.find(diff) != sum_map.end())
                {
                    count += sum_map[diff];
                }
            }
        }
        return count;
    }
};

3.三数之和（重点）

https://leetcode.cn/problems/3sum/description/

• 这道题不适合用哈希法，哈希法可以通过O(N^2)的for循环得到两个数的和，并存放在哈希表中，再通过差值寻找第三个数，但这样会造成重复下标，去重的过程很麻烦；
• 可以使用双指针法
  
• 拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。
• 依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。
• 接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
• 如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
  时间复杂度：O(n^2)。
• 最重要的部分其实是去重
• a的去重
  都是和 nums[i]进行比较，是比较它的前一个，还是比较它的后一个。
  如果仅比较后一个：
  
  那我们就把 三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断 下一个也是-1，那这组数据就pass了。
  不能有重复的三元组，但三元组内的元素是可以重复的！因此需要和前一个已经遍历过的数据对比；
  
• b与c的去重
  对b和c的去重如果放在找到三元组之前，就会漏掉0，0，0这种情况
  因此left和right的去重应放在找到三元组之后
  如果找到一个三元组后，left右边或者right左边是重复的，那么可以去掉，因为此时三元组有两个数已经确定了，这个三元组就是唯一的，因此重复的left或者right就需要去掉

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end()); // 先排序数组

        //begin从左向右遍历
        //left和right在begin的右边，计算三者的和，如果小于0，left++，如果大于0，right--
        //直到找到目标数字或者left和right越界或者相遇
        for(int begin = 0; begin < nums.size() - 2; begin++)
        {
            //如果begin > 0，就不需要往后寻找了
            if(nums[begin] > 0)
            {
                break;
            }

            //begin去重：不能简单地依据nums[begin] == nums[begin + 1]来去重，这样会漏掉-1，-1,2这种情况
            if(begin > 0 && nums[begin] == nums[begin - 1])
            {
                continue;
            }

            int left = begin + 1, right = nums.size() - 1;
            while(left < right)
            {
                //对left和right的去重如果放在找到三元组之前，就会漏掉0，0,0这种情况
                int sum = nums[begin] + nums[left] + nums[right];
                if(sum < 0)
                {
                    left++;
                }
                else if(sum > 0)
                {
                    right--;
                }
                else
                {
                    //因此left和right的去重应放在找到三元组之后
                    while(left < right && nums[left] == nums[left + 1])
                    {
                        left++;
                    }

                    while(left < right && nums[right] == nums[right - 1])
                    {
                        right--;
                    }
                    res.push_back(vector<int>{nums[begin], nums[left], nums[right]});
                    //找到之后左右指针同时移动
                    left++;
                    right--;
                }
            }

        }
        return res;
    }
};