查找重复数

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1:

输入: [1,2,3,1]
输出: true
示例 2:

输入: [1,2,3,4]
输出: false
示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

解题思路

1. 暴力查找，在这里我们采用了线性查找算法(最简单对查找算法)，来检查特定值是否存在列表中。做法就是逐个检查列表中的元素，直到找到满足条件的元素。

   即：循环表里全部nums数组，对第i 个整数nums[i]，对前i-1个整数查找nums[i]对重复值，如果找到，则返回True，否则继续。直到程序最后，返回False

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            i1 = nums[i]
            for j in range(1+i, len(nums)):
                j1 = nums[j]
                if(i1 == j1):
                    return True
        return False

​ 复杂度分析：时间复杂度:O(n2)，最坏的情况检查n(n+1)/2对整数

​ 空间复杂度: O(1)，只使用了常数空间

2. 排序

   如果存在重复元素，排序后它们应该相邻

   class Solution:
       def containsDuplicate(self, nums: List[int]) -> bool:
           lens = len(nums)
           if(lens == 0 or lens == 1):
               return False
           nums.sort()
           for i in range(len(nums) -1):
               if(nums[i] == nums[i+1]):
                   return True
           return False
   

   复杂度分析：排序的复杂度是 O(nlogn)，扫描的复杂度是O(n)。整个算法主要由排序过程决定，因此是O(nlogn)。

   ​ 空间复杂度: O(1)，只使用了常数空间

3. 哈希表

   利用支持快速搜索和插入操作的动态数据结构。

   使用搜索时间更快的数据结构将加快整个算法的速度。

   若nums[i]不在hash中，则令nums[i]为key，1为value，若已存在，则返回True，遍历数组到最后，则返回False

   class Solution:
       def containsDuplicate(self, nums: List[int]) -> bool:
           hash_v = {}
           for i in range(len(nums)):
               if(nums[i] not in hash_v):
                   hash_v[nums[i]] = 1
               else: 
                   return True
           return False
   

复杂度分析：时间复杂度:O(n)，只进行了一次遍历

​ 空间复杂度: O(n)，使用了hash存储过程