通关算法题之 ⌈哈希表⌋

哈希表

387. 字符串中的第一个唯一字符

给定一个字符串 s ，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1 。

输入: s = "leetcode"
输出: 0
输入: s = "loveleetcode"
输出: 2
1
2
3
4

考察哈希表的使用。

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> map;
        for(char ch : s){
            map[ch]++;
        }
        for(int i = 0; i < s.size(); i++){
            if(map[s[i]] == 1){
                return i;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

217. 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

输入：nums = [1,2,3,1]
输出：true
输入：nums = [1,2,3,4]
输出：false
1
2
3
4

哈希表：

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> set;
        for(int num : nums){
            if(set.count(num)){
                return true;
            }
            set.insert(num);
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

219. 存在重复元素 II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

输入：nums = [1,2,3,1], k = 3
输出：true
输入：nums = [1,0,1,1], k = 1
输出：true
输入：nums = [1,2,3,1,2,3], k = 2
输出：false
1
2
3
4
5
6

哈希表：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        int length = nums.size();
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            if (map.count(num) && i - map[num] <= k) {
                return true;
            }
            map[num] = i;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

187. 重复的DNA序列

DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。例如，"ACGAATTCCG" 是一个 DNA序列 。在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
解释：子串 "AAAAACCCCC" 和 "CCCCCAAAAA" 都重复出现了两次。
1
2
3

哈希表：

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int n = s.size();
        unordered_set<string> set, res;
        for(int i = 0; i <= n - 10; i++){
            string str = s.substr(i, 10);
            if(set.count(str)){
                res.insert(str);
            }
            set.insert(str);
        }
        return vector<string>(res.begin(), res.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊n / 2⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

输入：nums = [3,2,3]
输出：3
1
2

哈希表：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> map;
        for(int num : nums){
            map[num]++;
        }
        for(auto m : map){
            if(m.second > n / 2){
                return m.first;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

消消乐：

使用两个变量，一个存储要比较的元素，一个存储当前剩余的可以比较消除的次数。在遍历的过程中，遇到相同的数字则将次数加一，遇到不同的数字则减一，若是遇到零，则更新当前元素，重新计数比较。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 1;
        int maj = nums[0];
        for(int i = 1; i < nums.size(); i++){
            if(maj == nums[i]){
                count++;
            }else{
                count--;
                if(count == 0){
                    // 此时与nums[i]相同和不同的元素个数相等
                    maj = nums[i + 1];
                }
            }
        }
        return maj;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

229. 多数元素 II

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n / 3 ⌋ 次的元素。

输入：nums = [3,2,3]
输出：[3]
1
2

哈希表：

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> map;
        vector<int> res;
        for(int num : nums){
            map[num]++;
        }
        for(auto m : map){
            if(m.second > n / 3){
                res.push_back(m.first);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
1
2

输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序，使用 unordered_set。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> res;
        unordered_set<int> set(nums1.begin(), nums1.end());
        for(int num : nums2){
            if(set.count(num)){
                res.insert(num);
            }
        }
        return vector<int>(res.begin(), res.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

输入: s = "anagram", t = "nagaram"
输出: true
1
2

定义一个数组叫做record用来上记录字符串s里字符出现的次数。需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。这样就将字符串s中字符出现的次数，统计出来了。

那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。最后检查一下，**record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。**最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> map;
        for(char ch : s){
            map[ch]++;
        }
        for(char ch : t){
            map[ch]--;
        }
        for(auto m : map){
            if(m.second != 0){
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。

输入：nums = [1,1,1], k = 2
输出：2
1
2

输入：nums = [1,2,3], k = 3
输出：2
1
2

遍历数组nums，计算从第0个元素到当前元素的和，用哈希表保存出现过的累积和sum的次数。如果sum - k在哈希表中出现过，则代表从当前下标i往前有连续的子数组的和为sum。时间复杂度为$O(n)$，空间复杂度为$O(n)$。

class Solution {
public:
    int subarraySum(vector<int> &nums, int k) {
        int sum = 0, res = 0;
        unordered_map<int, int> map;
        map[0] = 1;
        for (int &num : nums) {
            sum += num;
            res += map[sum - k];
            map[sum]++;
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
1
2

由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        /* 根据返回值定义存储结果的变量 */
        vector<vector<string>> result;
        unordered_map<string, vector<string>> map;
        for (string& str: strs) {
            string key = str;
            /* 将串排序后便于统一作为键 */
            sort(key.begin(), key.end());
            /* 将相同键值的字符串放入vector容器中 */
            map[key].push_back(str);
        }
        /* 取出相同键值的vector */
        for (auto it = map.begin(); it != map.end(); ++it){
            result.push_back(it->second);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20