1346. Check If N and Its Double Exist

發表於 | 分類於

problem

solution

option 1 - hash table

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        int n = arr.size();
        unordered_set<int> s;
        for(int i=0;i<n;++i){
            
            if(s.find(arr[i]*2)!=s.end()) return true;
            if(arr[i]%2==0 && s.find(arr[i]/2)!=s.end()) return true;
            
            s.insert(arr[i]);
        }
        return false;
    }
};

analysis

  • time complexity O(nlogn)
  • space complexity O(1)