[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;
    }
};

、ソート法.配列をソートし、配列をスキャンします.隣接する2つの数が同じ場合は、重複要素が含まれます.そうでない場合はありません.この方法は時間的複雑度がO(nlogn),空間的複雑度がO(1)【並べ替え方法に依存する】であるが,leetcodeでは1方法よりも速く飛び出し,1方法でsetを構築するのに時間がかかるため,テスト例の問題もある.

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;
    }
};