217.Contains Duplicate I

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

判断数组中是否有重复元素系列中的第一题，最容易想到的办法是双指针法，也就是双重循环，O(n^2)的时间复杂度。不过通过排序，可以将时间复杂度降低到O(n)，代码如下:

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

这道题也可以用hash_table来完成，不过还是需要一次循环，意义不大。