Java 数组怎么实现寻找数组中重复数字或判断是否有重复元素的哈希与双指针解法-java教程-PHP中文网

哈希表法通用高效，时间o(n)空间o(n)；快慢指针仅适用于值域[1,n]且长度为n+1的数组，利用floyd判圈找环入口。

java 数组怎么实现寻找数组中重复数字或判断是否有重复元素的哈希与双指针解法

Java 中寻找数组中重复数字或判断是否存在重复元素，常用方法有哈希表（HashSet）和双指针（仅适用于特定条件）。但需注意：**双指针本身不能直接用于一般数组判重，它只在数组有序或满足“值域在 [1, n] 且长度为 n+1”等特殊前提下，配合快慢指针（Floyd 判圈）才能解决重复问题**。下面分场景说明两种主流解法的适用条件、原理与代码实现。

哈希表解法（通用、推荐）

适用于任意整型/对象数组，时间复杂度 O(n)，空间复杂度 O(n)。核心思路是遍历数组，将元素逐个加入 HashSet；若某元素已存在，则找到重复。

Alibabacloud Sdk Client Initialization For Java

在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。

下载

用 HashSet.add() 方法——该方法返回 boolean：true 表示新增成功，false 表示已存在
遇到 add() 返回 false 时立即返回该元素（找第一个重复）或返回 true（仅判断是否存在）
若需找出所有重复元素，可用 HashMap 记录频次，再遍历筛选 value > 1 的 key

示例（找第一个重复数字）：

public static int findFirstDuplicate(int[] nums) {
    Set<integer> seen = new HashSet();
    for (int num : nums) {
        if (!seen.add(num)) { // add 失败说明已存在
            return num;
        }
    }
    return -1; // 无重复
}</integer>

快慢指针解法（限特定条件：数组值域为 [1, n]，长度为 n+1）

这不是传统双指针（如左右指针），而是将数组视为链表（索引→值为指针），利用 Floyd 判圈算法找环入口——即重复元素。前提必须满足：所有元素 ∈ [1, n]，且数组长度为 n+1（鸽巢原理保证必有重复，且可构建环）。

把 i 当作节点，nums[i] 当作 next 指针指向的下一个索引
重复值会导致多个索引指向同一位置 → 形成环，环入口即为重复数字
分两步：先用快慢指针相遇确认有环；再用新指针从起点出发，与慢指针同步走，相遇点即环入口

示例（LeetCode 287. 寻找重复数）：

public static int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[0];
    // 第一步：找相遇点
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    
    // 第二步：找环入口（重复数）
    int ptr1 = nums[0], ptr2 = slow;
    while (ptr1 != ptr2) {
        ptr1 = nums[ptr1];
        ptr2 = nums[ptr2];
    }
    return ptr1;
}

其他常见变体与注意事项

排序后相邻比较：时间 O(n log n)，空间 O(1)，适合不允许额外空间且可修改原数组的场景
负号标记法（仅限正整数且范围合适）：遍历中将 nums[num] 取反，若发现已是负数，说明 num 重复。需注意绝对值还原和越界保护
双指针（左右指针）无法直接判重——它常用于两数之和、滑动窗口等有序或区间问题，对无序数组判重无意义
Java 8 Stream 可简写判断：Arrays.stream(nums).boxed().collect(Collectors.toSet()).size()