Leetcode.217.Contains Duplicate

题目

给定一个数组, 判断是否有重复的数字.

Input: [1,2,3,1]
Output: true
Input: [1,2,3,4]
Output: false

思路1

排序, 然后遍历判断相邻数字是否相等.

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

思路2

使用map, 判断map是否有该数字, 没有则加入map.

bool containsDuplicate(vector<int>& nums) {
    unordered_map<int, int> map;

    for(int num : nums) {
        if (map.count(num) > 0) {
            return true;
        }
        map[num] = num;
    }
    return false;
}

总结

空间换时间, 时间换空间. 还可以使用set等, 具体应用场景, 需要具体考虑.