LeetCode: 217 Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example:

Input: nums = [1,2,3,1]
Output: true

Input: nums = [1,2,3,4]
Output: false

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

问题

给定一个整数数组 nums，如果任何值在数组中至少出现两次，返回 true；如果数组中的每个元素都是唯一的，返回 false。

解决方案 1

使用哈希表来检查是否存在重复元素。

Approach 1 / 方法 1

遍历数组，将每个元素添加到哈希表中。如果在添加之前哈希表中已经存在该元素，则返回 true。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. Initialize an empty hash set.
   初始化一个空的哈希集合。

Step 1 / 第一步:

2. Iterate through the array and for each element, check if it exists in the hash set.
   遍历数组，对于每个元素，检查它是否存在于哈希集合中。

Step 2 / 第二步:

3. If the element exists in the hash set, return true.
   如果元素存在于哈希集合中，返回 true。

Step 3 / 第三步:

4. If the element does not exist, add it to the hash set.
   如果元素不存在，将其添加到哈希集合中。

Implementation / 实现

python

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        num_set = set()
        for num in nums:
            if num in num_set:
                return true
            num_set.add(num)
        return false

Explanation / 解释

1. Step 1 / 第一步:

• Initialize an empty hash set num_set.
  初始化一个空的哈希集合 num_set。

2. Step 2 / 第二步:

• For each element in the array, check if it is already in num_set.
  对于数组中的每个元素，检查它是否已经存在于 num_set 中。

3. Step 3 / 第三步:

• If the element is found in num_set, return true.
  如果在 num_set 中找到该元素，返回 true。

4. Step 4 / 第四步:

• If the element is not found, add it to num_set.
  如果未找到该元素，将其添加到 num_set 中。

Complexity Analysis / 复杂度分析

• Time Complexity: O(N), where N is the number of elements in the array.
  时间复杂度: O(N)，其中 N 是数组中的元素数量。

• Space Complexity: O(N), for storing the elements in the hash set.
  空间复杂度: O(N)，用于存储哈希集合中的元素。

Key Concept / 关键概念

• The key concept is to use a hash set to keep track of seen elements and quickly check for duplicates.
  关键概念是使用哈希集合跟踪已见的元素，并快速检查重复元素。

解决方案 2

先对数组进行排序，然后检查相邻元素是否相同。

Approach 2 / 方法 2

对数组进行排序，然后遍历数组，检查相邻元素是否相同。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. Sort the array.
   对数组进行排序。

Step 1 / 第一步:

2. Iterate through the sorted array and check if any adjacent elements are the same.
   遍历排序后的数组，检查是否有相邻元素相同。

Implementation / 实现

python

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return true
        return false

Explanation / 解释

1. Step 1 / 第一步:

• Sort the array nums.
  对数组 nums 进行排序。

2. Step 2 / 第二步:

• Iterate through the sorted array and check if any adjacent elements are equal.
  遍历排序后的数组，检查是否有相邻元素相同。

Complexity Analysis / 复杂度分析

• Time Complexity: O(N log N), for sorting the array.
  时间复杂度: O(N log N)，用于排序数组。

• Space Complexity: O(1), assuming the sort is in-place.
  空间复杂度: O(1)，假设排序是就地进行的。

Key Concept / 关键概念

• The key concept is to use sorting to simplify the problem of checking for duplicates.
  关键概念是使用排序简化检查重复元素的问题。

Tips / 提示

• Remember that sorting changes the original order of elements.
  记住排序会改变元素的原始顺序。

Solution Template for similar questions / 提示

• The general approach can be applied to other problems involving checking for duplicates or repeated elements.
  通用方法可以应用于其他涉及检查重复元素或重复元素的问题。

5 more similar questions / 推荐5问题

1. LeetCode 219: Contains Duplicate II
2. LeetCode 220: Contains Duplicate III
3. LeetCode 41: First Missing Positive
4. LeetCode 136: Single Number
5. LeetCode 287: Find the Duplicate Number

More

• LeetCode Explore – Hash Table
• GeeksforGeeks – Hashing
• InterviewBit – Hashing Interview Questions
• Algorithm 20 days by uwspstar

Recommended Resources:

LeetCode Question #217: Contains Duplicate by Algo Engine