哈希表

217. 存在重复元素

https://leetcode.cn/problems/contains-duplicate

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

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> Hash;
        for(auto i : nums){
            if(Hash.count(i)) return true;
            else Hash.insert(i);
        }
        return false;
    }
};

哈希表基础使用，若插入后还能 count 到就说明在数组中出现了至少两次。

1. 两数之和

https://leetcode.cn/problems/two-sum/

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

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

开一个哈希表，每过一个就把值和下标存表里，这样查询时只需要 O(1) 的时间复杂度。

350. 两个数组的交集 II

https://leetcode.cn/problems/intersection-of-two-arrays-ii/

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_multiset<int> Hash;
        vector<int> result;
        for(int i = 0; i < nums1.size(); i++){
            Hash.insert(nums1[i]);
        }
        for(int i = 0; i < nums2.size(); i++){
            if(Hash.count(nums2[i])){
                Hash.erase(Hash.find(nums2[i]));
                result.push_back(nums2[i]);
            }
        }
        return result;
    }
};

不难，但需要注意我们这里使用的是 unodered_multiset ，这个哈希集支持有多个相同的数，并且在删除的时候使用 Hash.find() ，因为如果直接删除的话会把所有这个数删掉。

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

https://leetcode.cn/problems/first-unique-character-in-a-string/

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

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> Hash;
        for(int i = 0; i < s.length(); i++){
            Hash[s[i]]++;
        }
        for(int i = 0; i < s.length(); i++){
            if(Hash[s[i]] == 1) return i;
        }
        return -1;
    }
};

用哈希表存，然后遍历两次即可。

383. 赎金信

https://leetcode.cn/problems/ransom-note/

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> h;
        for(int i = 0; i < magazine.length(); i++){
            h[magazine[i]]++;
        }
        for(int i = 0; i < ransomNote.length(); i++){
            h[ransomNote[i]]--;
            if(h[ransomNote[i]] < 0) return false;
        }
        return true;
    }
};

用哈希表存，遍历两个字符串即可。

242. 有效的字母异位词

https://leetcode.cn/problems/valid-anagram/

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> h1, h2;
        for(int i = 0; i < s.length(); i++){
            h1[s[i]]++;
        }
        for(int i = 0; i < t.length(); i++){
            h2[t[i]]++;
        }
        return h1 == h2;
    }
};

用两个哈希表来存，最后判断是否相等即可。

141. 环形链表

https://leetcode.cn/problems/linked-list-cycle/

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

哈希表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> seen;
        while (head) {
            if (seen.count(head)) return true;
            seen.insert(head);
            head = head->next;
        }
        return false;
    }
};

遍历链表观察是否有相同的节点，如果有就说明是环形链表。

快慢指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head || !head->next) return false;
        auto slow = head, fast = head->next;
        while (fast && fast->next) {
            slow = slow->next, fast = fast->next->next;
            if(fast == slow) return true;
        }
        return false;
    }
};

快的比慢的跑得快，总的遇到，要不然就是没有，直接返回 false。

349. 两个数组的交集

https://leetcode.cn/problems/intersection-of-two-arrays/

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

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int, int> h1, h2;
        for(int i = 0; i < nums1.size(); i++){
            h1[nums1[i]]++;
        }
        for(int i = 0; i < nums2.size(); i++){
            if(h1[nums2[i]] != 0 && h2[nums2[i]] == 0){
                res.push_back(nums2[i]);
                h2[nums2[i]]++;
            }
        }
        return res;
    }
};

两个哈希表即可解决问题，第二个哈希表用于判断答案里是否已经有这个元素了。

454. 四数相加 II

https://leetcode.cn/problems/4sum-ii/

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> h;
        int n = nums1.size();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                h[nums1[i] + nums2[j]]++;
            }
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                res += h[- nums3[i] - nums4[j]];
            }
        }
        return res;
    }
};

用一个哈希表存两个数的和，再遍历另外两个数看是不是相反数，总和为 0 时就把哈希表中存的个数加到答案里面。

169. 多数元素

https://leetcode.cn/problems/majority-element/

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int len = nums.size() / 2;
        unordered_map<int, int> S;
        for(int i = 0; i < nums.size(); i++) {
            S[nums[i]]++;
            if(S[nums[i]] > len) return nums[i];
        }
        return 0;
    }
};

按题意使用哈希即可。

128. 最长连续序列

https://leetcode.cn/problems/longest-consecutive-sequence/

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> hash;
        int res = 0;
        for(int n : nums) hash.insert(n);
        for(int n : hash) {
            if(hash.count(n - 1)) continue;
            int curNum = n, curLen = 1;
            while(hash.count(curNum + 1)) {
                curNum += 1;
                curLen += 1;
            }
            res = max(res, curLen);
        }
        return res;
    }
};

560. 和为 K 的子数组

https://leetcode.cn/problems/subarray-sum-equals-k/

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

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        int ans = 0, preSum = 0;
        hash[0] = 1;
        for(auto num : nums) {
            preSum += num;
            if(hash.count(preSum - k)) ans += hash[preSum - k];
            hash[preSum]++;
        }
        return ans;
    }
};

718. 最长重复子数组

https://leetcode.cn/problems/maximum-length-of-repeated-subarray/

给两个整数数组 nums1 和 nums2 ，返回两个数组中公共的、长度最长的子数组的长度。

class Solution {
public:
    typedef unsigned long long ULL;
    vector<ULL> ha, hb, p;
    const int P = 131;
    int m, n;
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        m = nums1.size(), n = nums2.size();
        ha.resize(m + 1), hb.resize(n + 1), p.resize(m + 1);
        for(int i = 1; i <= m; i++) ha[i] = ha[i - 1] * P + nums1[i - 1];
        for(int i = 1; i <= n; i++) hb[i] = hb[i - 1] * P + nums2[i - 1];
        p[0] = 1;
        for(int i = 1; i <= m; i++) p[i] = p[i - 1] * P;
        int l = 0, r = m;
        while(l < r) {
            int mid = l + r + 1 >> 1;
            if(check(mid)) l = mid;
            else r = mid - 1;
        }
        return r;
    }

    bool check(int mid) {
        unordered_set<ULL> s;
        for(int i = mid; i <= m; i++) s.insert(get(ha, i - mid + 1, i));
        for(int i = mid; i <= n; i++) {
            if(s.count(get(hb, i - mid + 1, i))) return true;
        }
        return false;
    }

    ULL get(vector<ULL>& h, int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
};

Previous动态规划 Next双指针

Last updated 1 year ago