算法题 存在重复元素

217. 存在重复元素

问题描述

给定一个整数数组 nums，判断其中是否存在重复元素。如果存在重复元素，返回 true；否则返回 false。

示例：

示例 1：

输入：nums = [1,2,3,1]

输出：true

解释：

元素 1 在下标 0 和 3 出现。

示例 2：

输入：nums = [1,2,3,4]

输出：false

解释：

所有元素都不同。

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]

输出：true

算法思路

方法一：哈希集合（Set）

优点：时间效率高，逻辑清晰
适用场景：通用解法，适合大多数情况

方法二：排序后比较相邻元素

优点：空间复杂度更低（原地操作）
缺点：修改了原数组结构，不适用于不允许修改输入的场景

代码实现

方法一：使用 HashSet 判断重复（推荐解法）

import java.util.HashSet;
import java.util.Set;

class Solution {
/**
* 判断数组中是否存在重复元素（使用HashSet）
*
* 核心思想：利用HashSet的唯一性特性，
* 在添加元素时自动检测是否已存在相同元素。
*
* @param nums 整数数组
* @return 存在重复返回true，否则返回false
*/
public boolean containsDuplicate(int[] nums) {
// 创建HashSet用于存储已遍历的元素
// HashSet特点：不允许重复元素，查找和插入均为O(1)
Set<Integer> seen = new HashSet<>();

// 遍历数组中的每一个元素
for (int num : nums) {
// 尝试将当前元素加入HashSet
// add()方法返回boolean值：
// – 如果元素不存在则添加成功，返回true
// – 如果元素已存在则添加失败，返回false
if (!seen.add(num)) {
// 添加失败说明该元素已经存在 → 发现重复
return true;
}
// 如果添加成功，继续处理下一个元素
}

// 所有元素都成功添加，说明没有重复元素
return false;
}
}

方法二：排序后检查相邻元素（空间优化解法）

import java.util.Arrays;

class Solution {
/**
* 判断数组中是否存在重复元素（排序法）
*
* 核心思想：排序后重复元素必定相邻，
* 只需一次遍历检查相邻元素即可。
*
* 注意：此方法会改变原数组顺序
*
* @param nums 整数数组
* @return 存在重复返回true，否则返回false
*/
public boolean containsDuplicate(int[] nums) {
// 对数组进行排序
// 排序后相同的元素会聚集在一起
Arrays.sort(nums);

// 遍历排序后的数组，检查相邻元素
// 从索引1开始，比较当前元素与前一个元素
for (int i = 1; i < nums.length; i++) {
// 如果当前元素等于前一个元素 → 存在重复
if (nums[i] == nums[i – 1]) {
return true;
}
}

// 遍历完成未发现相邻重复元素 → 无重复
return false;
}
}

算法分析

• 时间复杂度：

  • 方法一（HashSet）：O(n)
    • 遍历数组一次：O(n)
    • HashSet的add操作平均O(1)
  • 方法二（排序）：O(n log n)
    • 排序时间复杂度：O(n log n)
    • 遍历检查相邻元素：O(n)
    • 总体由排序主导

• 空间复杂度：

  • 方法一：O(n)
    • HashSet最多存储n个元素
  • 方法二：O(1) 或 O(log n)
    • 不考虑排序的递归栈空间时为O(1)
    • 快速排序/归并排序的递归调用栈为O(log n)

• 方法对比：

  方法时间复杂度空间复杂度是否修改原数组适用场景

  HashSet	O(n)	O(n)	否	通用推荐，性能最优
  排序法	O(n log n)	O(1)/O(log n)	是	内存受限且允许修改输入

算法过程

输入：nums = [1,2,3,1]

方法一：HashSet 过程

方法二：排序法过程

测试用例

public static void main(String[] args) {
Solution solution = new Solution();

// 测试用例1：存在重复（示例1）
int[] nums1 = {1,2,3,1};
System.out.println("Test 1: " + solution.containsDuplicate(nums1)); // true

// 测试用例2：无重复（示例2）
int[] nums2 = {1,2,3,4};
System.out.println("Test 2: " + solution.containsDuplicate(nums2)); // false

// 测试用例3：两个相同元素
int[] nums3 = {1,1};
System.out.println("Test 3: " + solution.containsDuplicate(nums3)); // true

// 测试用例4：单元素
int[] nums4 = {1};
System.out.println("Test 4: " + solution.containsDuplicate(nums4)); // false

// 测试用例5：空数组
int[] nums5 = {};
System.out.println("Test 5: " + solution.containsDuplicate(nums5)); // false

// 测试用例6：多个重复
int[] nums6 = {1,2,3,4,2};
System.out.println("Test 6: " + solution.containsDuplicate(nums6)); // true

// 测试用例7：负数重复
int[] nums7 = {–1,–2,–1};
System.out.println("Test 7: " + solution.containsDuplicate(nums7)); // true

// 测试用例8：大数组无重复
int[] nums8 = new int[1000];
for (int i = 0; i < 1000; i++) {
nums8[i] = i;
}
System.out.println("Test 8: " + solution.containsDuplicate(nums8)); // false
}

关键点

常见问题