[Algorithm][哈希表][两数之和][判定是否互为字符重排][存在重复元素][存在重复元素Ⅱ][字母异位词分组]详细讲解

---

0.原理讲解

• 哈希表有啥用？
  • 快速查找某个元素 -> $O(1)$
  • 但是，空间复杂度：$O(N)$
• 什么时候用哈希表？
  • 频繁地查找某一个数的时候
• 怎么用哈希表？
  • STL容器
  • 用数组模拟简易哈希表 -> 快
    • 字符串中的"字符"
    • 数据范围很小的时候 -> $1\sim 10^{3\sim 7}$

---

1.两数之和

1.题目链接

• 两数之和

---

2.算法原理详解

• 思路：如果事先将「数组内的元素」和「下标」绑定在⼀起存⼊「哈希表」中，然后直接在哈希表中查找每⼀个元素的target - nums[i]，就能快速的找到「⽬标和的下标」
• 做法：使用哈希表来优化暴力解法
  • 先固定一个数
  • 依次与该数之前的数相加
• 为什么是与该数之前的数相加，而不是往后找？
  • 如果实现把数都放到哈希表中，可能会找到另一个数是自己的情况，避免特判
  • 同时，也避免了二次遍历

---

3.代码实现

vector<int> TwoSum(vector<int>& nums, int target) 
{
    unordered_map<int, int> hash; // <nums[i], i>
    for(int i = 0; i < nums.size(); i++)
    {
        int tmp = target - nums[i];
        if(hash.count(tmp))
        {
            return {hash[tmp], i};
        }

        hash[nums[i]] = i;
    }

    return {-1, -1};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

2.判定是否互为字符重排

1.题目链接

• 判定是否互为字符重排

---

2.算法原理详解

• 思路：使用两个哈希表，判断两个哈希表是否相等即可
• 优化：只使用一个哈希表
  • 第一个字符串hash[x]++
  • 第二个字符串hash[x]--
  • 如果出现< 0的，则不构成重排

---

3.代码实现

bool CheckPermutation(string s1, string s2) 
{
    if(s1.size() != s2.size()) 
    {
        return false;
    }

    int hash[26] = { 0 };
    for(auto& ch : s1)
    {
        hash[ch - 'a']++;
    }

    for(auto& ch : s2)
    {
        hash[ch - 'a']--;
        if(hash[ch - 'a'] < 0)
        {
            return false;
        }
    }

    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

3.存在重复元素

1.题目链接

• 存在重复元素

---

2.代码实现

bool ContainsDuplicate(vector<int>& nums) 
{
    unordered_set<int> hash; // <nums[i]>
    for(auto& x : nums)
    {
        if(hash.count(x))
        {
            return true;
        }
        else
        {
            hash.insert(x);
        }
    }

    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

4.存在重复元素 II

1.题目链接

• 存在重复元素 II

---

2.算法原理详解

• 细节：如果数组内存在⼤量的「重复元素」，⽽判断下标所对应的元素是否符合条件的时候，需要将不同下标的元素作⽐较，怎么处理这个情况呢？
  • 按照下标「从⼩到⼤」的顺序遍历数组，当遇到两个元素相同，并且⽐较它们的下标时，这两个下标⼀定是距离最近的，因为：
    • 如果当前判断符合条件直接返回 true ，⽆需继续往后查找
    • 如果不符合条件，那么前⼀个下标⼀定不可能与后续相同元素的下标匹配(因为下标在逐渐变⼤)，那么可以⼤胆舍去前⼀个存储的下标，转⽽将其换成新的下标，继续匹配

---

3.代码实现

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

        hash[nums[i]] = i;
    }

    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

5.字母异位词分组

1.题目链接

• 字母异位词分组

---

2.算法原理详解

• 如何判断两个字符串是否是异位词？
  • 异位词排序后，两个单词应该是完全相同的
• 如何分组？
  • hash<string, vector<string>>
  • 将排序后的string当做哈希表的key值
  • 将字⺟异位词数组(string[])当成val值

---

3.代码实现

vector<vector<string>> GroupAnagrams(vector<string>& strs) 
{
    unordered_map<string, vector<string>> hash;
    for(auto& str : strs)
    {
        string tmp = str;
        sort(tmp.begin(), tmp.end());
        hash[tmp].push_back(str);
    }

    vector<vector<string>> ret;
    for(auto& [x, y] : hash) // 这种写法积累下来
    {
        ret.push_back(y);
    }

    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18