hash表，O(n)空间复杂度

class Solution(object):
    def duplicateInArray(self, nums):
        """
        :type nums: List[int]
        :rtype int
        """
        n=len(nums)
        for i in range(0,n):
            if nums[i]<0 or nums[i]>=n:
                return -1

        hash_table = [0 for x in range(0,n)]

        for x in range(0,n):
            hash_table[nums[x]]+=1
            if hash_table[nums[x]]>1:
                return nums[x]

        return -1

O(1)空间复杂度

class Solution(object):
    def duplicateInArray(self, nums):
        """
        :type nums: List[int]
        :rtype int
        """
        n=len(nums)
        for i in nums:
            if i<0 or i>n-1:
                return -1

        for i in range(0,n):
            while nums[i]!=i and nums[nums[i]]!=nums[i]:
                temp = nums[i]
                nums[i]=nums[nums[i]]
                nums[temp]=temp

            if nums[i]!=i:
                return nums[i]

        return -1