Contains Duplicate I II III

Contains Duplicate I

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.

Solution

用set去重，比较set的大小和nums大小，变小了说明就有duplicate。

// Time:  O(n)
// Space: O(n)

    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> nums_set(nums.begin(), nums.end());
        return nums_set.size() != nums.size();
    }
//也可以不用所有的num都用来构建set，遇到重复的就退出。
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> myset;
        for(auto const& num : nums) {
            if(myset.find(num) != myset.end()) {
                return true;
            }
            myset.emplace(num);
        }
        return false;
    }

如果要O(1)space呢？

// Time:  O(nlogn)
// Space: O(1)
class Solution2 {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return unique(nums.begin(), nums.end()) != nums.end();
    }
};
//或者这样：
public boolean containsDuplicate(int[] nums) {

        Arrays.sort(nums);
        for(int ind = 1; ind < nums.length; ind++) {
            if(nums[ind] == nums[ind - 1]) {
                return true;
            }
        }
        return false;
    }

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.

Solution

要么暴力，要么用hash记录number出现的位置，再次出现的时候看index differece是不是小于等于K的。

// Time:  O(n)
// Space: O(n)

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> lookup;
        for (int i = 0; i < nums.size(); ++i) {
            if (lookup.find(nums[i]) == lookup.end()) {
                lookup[nums[i]] = i;
            } else {
                // It the value occurs before, check the difference.
                if (i - lookup[nums[i]] <= k) {
                    return true;
                }
                // Update the index of the value.
                lookup[nums[i]] = i;
            }
        }
        return false;
    }
};

网上的牛逼解法：维护一个大小为K的set

//Time: O(nlogk)
//Space: O(K)
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        set<int> cand;
        for (int i = 0; i < nums.size(); i++) {
            if (i > k) cand.erase(nums[i-k-1]);
            if (!cand.insert(nums[i]).second) return true;
        }
        return false;
    }

暴力：O(nk) run time, O(1) space

bool containsNearbyDuplicate(vector<int>& nums, int k) {
        for(int i=0; i<nums.size()-k; i++) {
            //j-i <=k
            for(int j = i+1; j<=k+i; j++) {
                if(nums[i] == nums[j]) return true;
            }
        }
        return false;
    }

Contains 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.

Solution

维护一个sliding window (因为要删除最早的元素当window size大于k的时候，所以用queue） 和BST（因为有重复的元素所以用multiset）

// Time:  O(nlogk)
// Space: O(k)

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if (k < 0 || t < 0) {
            return false;
        }

        queue<int64_t> window;
        multiset<int64_t> bst;
        for (int i = 0; i < nums.size(); ++i) {
            // Only keep at most k elements.
            if (bst.size() > k) {
                int num = window.front();
                window.pop();
                bst.erase(bst.find(num));
            }
            // Every search costs time: O(logn).
            const auto it = bst.lower_bound(nums[i] - t);
            if (it == bst.cend() || (*it - nums[i]) > t) {
                // Not found.
                window.emplace(nums[i]);
                bst.emplace(nums[i]);
            } else {
                return true;
            }
        }
        return false;
    }
};

牛逼解法：用一个set做sliding window就可以了。

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<int> window; // set is ordered automatically 
        for (int i = 0; i < nums.size(); i++) {
            if (i > k) window.erase(nums[i-k-1]); // keep the set contains nums i j at most k
            // -t <= x - nums[i] <= t;
            auto pos = window.lower_bound(nums[i] - t); // x >= nums[i] - t
            if (pos != window.end() && *pos - nums[i] <= t) // x <= nums[i] + t
                   return true;
            window.insert(nums[i]);
        }
        return false;
    }
};