#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
void set_(int i) { a[i>>SHIFT] = (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
if(nums.size()==0)return false;
int i;
for (i = 0; i < nums.size(); i++)
clr(nums[i]);
for (i = 0; i < nums.size(); i++)
{
if(test(nums[i]))return true;
else set_(nums[i]);
}
return false;
}
};
20ms C++ use bitmap


yes,if we use bitmap, it is a restriction that we must consider the limit of data
If in the test case, there is a number no less than 10000000, the array will over flow.
And, if the number set is 0,1,20000000, there will be lots of no used space, and the array will over flow.all these are the defect of bitmap