【优选算法】哈希表

题目描述：

思路讲解：
本题可以使用暴力解法，先固定一个位置i，再在该位置的右边寻找target-nums[i]，找不到就将i向右移，直到找到target-nums[i]后返回下标i和target-nums[i]这个数的下标。

暴力解法还有另一个思路，就是先固定一个位置i，再在该位置的左边寻找target-nums[i]，找不到就将i向右移，直到找到target-nums[i]后返回下标i和target-nums[i]这个数的下标。两种思路基本一致，为什么要有第二种思路呢？因为第一种思路是大家通常会想到的，但是第二种方式是可以使用哈希表进行优化的。

接下来讲解如何使用哈希表优化第二种思路，定义一个哈希表unordered_map<int,int> um，um中的第一个int是用来存储数字的，um中第二个int是用来存储对应数字的下标，就是先固定一个位置i，查找um中是否存在一个数是target-nums[i]，若有则将下标i和target-nums[i]对应的下标返回，否则先将下标i对应的数字和下标i存入um中，再将i向右移动，重复上面的操作直到找到为止。

为什么不使用哈希表来优化第一种思路呢？因为使用第一种思路时，需要将所有的数加入到哈希表中，但是数组中会出现相同数，我们只能选择一个存入到哈希表中。当我们使用第一种思路来查找时，如果遇到了target-nums[i]=nums[i]的情况，我们并不知道数组中是否只存在一个nums[i]，所以这种情况就需要特殊处理，而使用第二种思路加上哈希表的优化就没有这个特殊情况需要处理，所以使用第二种情况加上哈希表优化来解决本题。

编写代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> um;
        int numsLen = nums.size();
        for(int i = 0 ; i < numsLen ; i++)
        {
            if(um.count(target - nums[i]) != 0)
                return {um[target - nums[i]],i};
            else
                um.insert(make_pair(nums[i],i));
        }        
        return {0,0};
    }
};

题目描述：

思路讲解：
当大家看到这题的时候，可能会想将一个字符串的所有排列组合的方式都找出来与另一个字符串相比较，但是这样的复杂度会非常的高，不推荐。

思路一，题目中讲到了字符串都是由小写字母组成的，我们定义两个整形数组int hash1[26],hash2[26]，将两个字符串分别遍历，将字符串中的字符出现的次数分别统计存储在hash1和hash2中，最后再遍历讲个数组中各个字符出现的次数是否相同。

思路二，我们定义一个整形数组int hash[26]，先将一个字符串遍历，并将字符串中的字符出现的次数分别统计存储在hash中，再遍历另一个字符串，在这个字符串中，每出现一个字符就在hash中对应字符的个数减一，最后遍历hash数组，若hash中出现有不为0的情况就说明这两个字符不为字符重排，若都为0则说明是字符重排。

本题还有一个优化的方案，当两个字符串的长度不同时，则说明这两个字符串必定不是字符重排。

编写代码：

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        int hash[26] = {0};
        if(s1.size() != s2.size())
            return false;
        
        for(auto ch : s1)
            hash[ch-'a']++;

        for(auto ch : s2)
            hash[ch-'a']--;

        for(int i = 0 ; i < 26 ;i++)
            if(hash[i] != 0)
                return false;

        return true;
    }
};

题目描述：

思路讲解：
本题与上面两数之和的思路基本一致，只是两数之和中查找的是um中是否存在一个数为target-nums[i]，而本题则是在um中查找是否存在一个数为nums[i]。

定义一个哈希表unordered_map<int,int> um，um中的第一个int是用来存储数字的，um中第二个int是用来存储对应数字的下标，就是先固定一个位置i，查找um中是否存在一个数是nums[i]，若有则返回true，否则先将下标i对应的数字和下标i存入um中，再将i向右移动，重复上面的操作直到找到返回true或i遍历完也没找到返回false。
编写代码：

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> us;
        int numsLen = nums.size();

        for(int i = 0 ; i < numsLen ;i++)
        {
            if(us.count(nums[i]) != 0)
                return true;
            else
                us.insert(nums[i]);
        }
        return false;
    }
};

题目描述：

思路讲解：
本题与上一题的思路基本一致，只是上一题是在um中查找是否存在一个数为nums[i]，而本题需要在上一题的基础上查看两者下标差的绝对值是否小于等于k。

定义一个哈希表unordered_map<int,int> um，um中的第一个int是用来存储数字的，um中第二个int是用来存储对应数字的下标，就是先固定一个位置i，查找um中是否存在一个数是nums[i]，并且这两种的下标差的绝对值是否小于等于k，就会出现下面三种情况：

1. 若是找到了并且下标差的绝对值小于等于k，则返回true，
2. 若是找到了但是下标差的绝对值大于k，更新um中nums[i]的下标为当前i的下标，再将i向右移动
3. 若是在um中没有找到nums[i]，先将下标i对应的数字和下标i存入um中，再将i向右移动

重复上面的操作直到找到返回true或i遍历完也没找到返回false。

编写代码：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> um;
        int numsLen = nums.size();
        for(int i = 0 ; i < numsLen ; i++)
        {
            if(um.count(nums[i]) != 0 && i - um[nums[i]] <= k)
                return true;
            else
                um[nums[i]] = i;
        }
        return false;
    }
};

题目描述：

思路讲解：
本题的难点是如何找到互为字母异位词的字符串，上面判定是否互为字符重排这道题目中就讲述了如何判断两个字符串是否互为字母异位词，但是这样会使得本道题的代码写起了有点麻烦，所以本道题将使用快速排序的方式将所有的字符串排序一遍，若排序后的字符串相同则代表则排序前的两个字符串互为字母异位词，虽然说使用快速排序会使本题的复杂度增大，但是会让本题写起了更加的轻松。

哈希表中并不是只能存储char，int，double等内置类型，还可以存储string、vector等容器，定义一个哈希表unordered_map<string,vector<string>> um，string中存储的是排序后的数组，vector<string>中存储的是所有排序后与前面string相同的字符串。遍历str中所有的字符串，遍历到一个字符串时，先将字符串排序，会有两种不同的情况

1. 若排序后的字符串在um中不存在，则{排序后的字符串，排序之前的字符串}存入到um中
2. 若排序后的字符串在um中存在，则将排序之前的字符串添加到um中排序之后相同的字符串数组中

除了完str所有的字符串以后，定义一个数组vector<vector<string>> ans，将um中所有数组复制到ans中，再返回ans即可解决本题。

编写代码：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> um;
        vector<vector<string>> ans;
        int strsLen = strs.size();
        for(int i = 0 ; i < strsLen ; i++)
        {
            string tmp = strs[i];
            sort(tmp.begin(),tmp.end());
            um[tmp].push_back(strs[i]);
        }
        
        for(auto& it : um)
            ans.push_back(it.second);

        return ans;
    }
};