Contains Duplicates

217. Contains Duplicates

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

S1: hashing (unordered_set) 用一个unordered_set来放已经扫描过的数。如果当前数已经出现在set里，则返回true.否则返回false.

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> history;
    for (int v : nums) {
        if (history.find(v) == history.end()) history.insert(v);
        else return true;
    }
    return false;
}

S2: sort

    bool containsDuplicate(vector<int>& nums) {
        int size = nums.size();
        sort(nums.begin(), nums.end());
        for(int i = 1; i < size; ++i){
            if(nums[i] == nums[i-1]) return true;
        }
        return false;
    }

219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

S1: use hashtable to store all index

    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, vector<int>> index;
        for(int i = 0; i < nums.size(); ++i){
            if(index[nums[i]].size() > 0){
                for(auto idx : index[nums[i]]) if(abs(i-idx) <= k) return true;
            }
            index[nums[i]].push_back(i);
        }
        return false;
    }

S2: hashing (unordered_set)

用unordered_set维护最近出现的k个数。当扫描到第j个数时： 把nums[j-k]从队列删除。 检查是否nums[j]在集合中 插入nums[j]

bool containsNearbyDuplicate(vector<int>& nums, int k) {
    if (k <= 0) return false;
    unordered_set<int> history;
    for (int j = 0; j < nums.size(); ++j) {
        if (j > k) history.erase(nums[j-k-1]);
        if (history.find(nums[j]) == history.end()) history.insert(nums[j]);
        else return true;
    }
    return false;
}

220. Contain Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

S: set / balanced BST O（nlogk)

这里用set(balanced search tree)而不是unordered_set(hashmap)因为对于set存储的值我们要进行iteration，而不是直接取出某一个值。 当扫描nums[j]时： 1.删除nums[j-k-1] 2.检查set中是否有[nums[j]-t, nums[j]+t]中的数（通过搜索lowerbound(nums[j]-t)) 3.插入nums[j]

    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<int> history;
        for(int i = 0; i < nums.size(); ++i){
            if(i > k) history.erase(nums[i-k-1]);
            auto candidate = history.lower_bound(nums[i]-t);//low_bound return the smallest value >= nums[i] - t
            //不要用*candidate<=nums[i]+t,因为右侧可能会溢出，做加法运算时要注意
            if(candidate != history.end() && *candidate - nums[i]<= t) return true;
            history.insert(nums[i]);
        }
        return false;
    }