基础知识

如果要使用集合解决哈希问题，优先使用效率最优的unordered_set，如果集合要求有序，那么就用set，如果不仅有序还有重复数据的话就用multiset

  1.     vector<int> v;
  2.     v.push_back(1);
  3.     v.push_back(2);
  4.     v.push_back(3);
  5.     unordered_set<int> uset{1,2,3};//赋值初始化
  6.     unordered_set<int> uset2(v.begin(),v.end());//迭代器初始化
  7.     for(auto x:uset) cout<<x<<' ';cout<<endl;
  8.     for(auto x:uset2) cout<<x<<' ';cout<<endl;
  9.     uset.insert(4);
  10.     for(auto x:uset) cout<<x<<' ';cout<<endl;
  11.     uset.erase(4);
  12.     for(auto x:uset) cout<<x<<' ';cout<<endl;
  13.     uset.emplace(4);//插入元素，效率比insert高
  14.     for(auto x:uset) cout<<x<<' ';cout<<endl;

哈希技巧一

将数组元素处理后放入哈希表里，可以不用一开始就把所有的数组放进去，而是处理一个放入一个。这样，新遍历的数组元素可以不与哈希表里的元素冲突，可以避免重复。

/*
给定一个整数数组 nums 和一个整数目标值 target。
请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
*/
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

哈希技巧二

在https://leetcode-cn.com/problems/4sum-ii/四数相加的题目中，我使用multiset存可能有重复的元素，超时了，应该用map存出现的次数。

哈希技巧三

剪枝https://leetcode-cn.com/problems/3sum/，要求a+b+c=0，先剪去a的重复，再用set维护c不会用到前一次的b值。不过这道题用双指针更好。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[j], c = -(a + b)
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零，那么不可能凑成三元组
            if (nums[i] > 0) {
                continue;
            }
            if (i > 0 && nums[i] == nums[i - 1]) { //三元组元素a去重
                continue;
            }
            unordered_set<int> set;
            for (int j = i + 1; j < nums.size(); j++) {
                if (j > i + 2
                        && nums[j] == nums[j-1]
                        && nums[j-1] == nums[j-2]) { // 三元组元素b去重
                    continue;
                }
                int c = 0 - (nums[i] + nums[j]);
                if (set.find(c) != set.end()) {
                    result.push_back({nums[i], nums[j], c});
                    set.erase(c);// 三元组元素c去重，在确定b和c的过程中c不再出现
                } else {
                    set.insert(nums[j]);
                }
            }
        }
        return result;
    }
};