[LeetCode] Contains Duplicate

Contains Duplicate

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.

解题思路：

1、哈希法。用一个set记录所有已经出现过的数字，若出现冲突，则包含重复元素，若不冲突，则不包含重复元素。此方法的时间复杂度为O(n)，空间复杂度为O（n）

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        set<int> s;
        int len=nums.size();
        for(int i=0; i<len; i++){
            if(s.find(nums[i])==s.end()){
                s.insert(nums[i]);
            }else{
                return true;
            }
        }
        return false;
    }
};

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

[LeetCode] Contains Duplicate

原文：http://blog.csdn.net/kangrydotnet/article/details/45970907