array

Contains Duplicate

image.png

[图片上传中...(image.png-d0fb52-1516785963782-0)]

利用set不能保存重复元素的特性，判断前后两个数组长度是否相同即可：

题目翻译

给定一个整数数组，判断其中是否包含重复元素。你要写的函数，当包含重复元素时返回 true，否则返回 false。

思路方法

首先我们可能会想到，遍历数组，对于每个元素，再检查后面所有元素是否有相同的就可以了。然而这样时间复杂度太高，会超时，所以不可取。

思路一

既然暴力查重不可取，那么我没先将数组进行排序（排序的复杂度），排序后比较每个元素与后一个元素是否相等即可。

代码

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        nums.sort()
        for i in xrange(0, len(nums)-1):
            if nums[i] == nums[i+1]:
                return True
        return False

思路二

通过字典（HashMap），将出现过的数记录下来，遍历下一个数时检查是否已经出现过。

代码

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        map = {}
        for i in nums:
            if i in map:
                return True
            map[i] = True
        return False

思路三

没有重复的数组相当于集合，利用Python的set，将数组转换成集合，若长度与原来相等则说明没有重复。

代码

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        return len(nums) != len(set(nums))