【刷题14】哈希表专题

一、两数之和

题目：

思路：哈希表<元素，下标>

• 遍历数组，k = 目标值-该位置的元素，在哈希表中找k
• 如果得到的j(下标)为0，说明k值之前没有存在哈希表中，跳过本次循环
• 找到了j，并且不等于i，因为不能是相同的位置，返回i和j

j = 0 会不会与找到的元素位置下标刚好为0(第一个元素)冲突？不会！因为能到这步的前提肯定是中间的某个元素与第一个元素相加等于target；既然如此，那么遍历到这个中间某个元素是不是之间就已经遍历过第一个元素了，既然刚开始就是第一个元素，那么为什么不这时候找k值呢？k值不就是这个中间的某个元素吗，然后j肯定不是0，并且i不等于j，直接返回就结束了。所以不会冲突。

代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for(int i=0; i<nums.size(); i++)
        {
            hash[nums[i]] = i;
        }
        for(int i=0; i<nums.size(); i++)
        {
            int k = target-nums[i];
            int j = hash[k];
            if(j==0) continue;// 不存在的元素
            if(i != j)// 防止重复
            {
                return {i, j};
            }
        }
        return {};
    }
};

二、判断是否互为字符重排

题目：

思路：

• 两个字符串长度不相同，直接返回false
• 分别用两个哈希表统计每个元素出现的个数
• 遍历其中一个字符串，如果该字符在另一个哈希表中不存在，返回false；遍历完后，返回true

代码：

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

三、存在重复元素

题目：

思路：
哈希表统计每个元素出现的个数，大于等于2就返回true，如果没有返回false

代码：

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int, int> hash;
        for(auto &e : nums)
            hash[e]++;
        for(auto &e : nums)
        {
            if(hash[e] >= 2) return true;
        }
        return false;
    }
};

四、存在重复元素ll

题目：

思路：
哈希表<元素，下标>

• 遍历，如果之前相同的元素出现过，用当前的坐标减去之前出现过的元素的下标，满足条件返回true；然后再<元素，下标>进入哈希表，注意：是先判断，再进入哈希表，所以相同的元素出现，该位置的下标i与哈希表的value值(也是下标)不同。如果顺序错了，之前的下标就被覆盖了

代码：

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

五、字母异位词分组

题目：

思路：
哈希表<字符串，字符串数组>

• 遍历strs，每个元素是字符串，先用临时的对象sort下，是相同位置就进入该字符串数组(哈希表的value)
• 然后给返回值，返回（注意写法）

代码：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ret;
        unordered_map<string, vector<string>> hash;
        for(auto &s : strs)
        {
            string t = s;
            sort(t.begin(), t.end());
            hash[t].push_back(s);
        }
        for(auto &[x, y]: hash)
        {
            ret.push_back(y);
        }
        return ret;
    }
};