Index | Diary 2024-03-12

思路

  1. [mine] 双指针，在超大数组的情况下超时
  2. 数组排序 then 遍历判断, 时间复杂度为 \(NlogN\)
  3. 哈希表 牺牲空间保时间，时间复杂度为 \(N\)

coding

  1. 创建一个 hash table, 从左往右遍历数组
  2. 检测 table 中书否已存在当前字符
    • if 存在，return true;
    • else 将当前字符加入 Hash table； 
          class Solution {
    public:
        bool containDuplicate(vector<int>& nums) {
            unordered_set<int> s;
            for (int x: nums) {
                if (s.find(x) != s.end()) { 
                    return true; 
                }
                s.insert(x);
            }
            return false;
        }
    }