217. 存在重复元素

排序

思路

首先对数组进行排序，然后对数组进行排序，遍历数组对 N 和 N+1 项进行比较，如果相等的话就是有重复的数据

export function containsDuplicate(nums: number[]): boolean {
    nums.sort((a, b) => a - b)

    for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i] === nums[i + 1]) {
            return true
        }
    }

    return false
}

复杂度分析

• 时间复杂度：O(N log N)，其中 N 为遍历 nums 的长度， logN 为 nums.sort 的消耗

• 空间复杂度：O(log N)，也就是 nums.sort 的复杂度

Map

思路

只需要遍历 nums 数组的元素，每一个都存储到对象 numMap 里面，如果有重复的数据即可得出结果

/**
 * 对象存储数据
 * @param nums 
 * @returns 
 */
export function containsDuplicate(nums: number[]): boolean {
    const numMap: { [key: number]: number } = {}

    for (let i of nums) {
        if (!numMap[i]) {
            numMap[i] = 1
        } else {
            return true
        }
    }
    return false
}

复杂度分析

• 时间复杂度：O(N)，最长时间为遍历 nums 数组所用的时间

• 空间复杂度：O(N)，最大空间为遍历 nums 的长度