如何在 Java 中利用数组的符号位标记法在不使用额外空间的前提下寻找数组中的重复项-java教程-PHP中文网

该方法利用数组本身作哈希表，通过符号位标记已出现数字：遍历中以abs(num)-1为下标，若对应值为正则取负标记，若已为负则abs(num)为重复项；要求元素范围为[1,n]、全为正整数、允许修改原数组。

java 中利用数组符号位标记法找重复项，核心思路是：把数组本身当作哈希表，用元素值作为下标，通过将对应位置的数取负来标记“该下标对应的数字已出现过”。当再次遇到相同下标位置已是负数时，说明当前数字重复。

前提条件与限制

该方法仅适用于满足以下条件的整型数组：

所有元素都在 [1, n] 范围内（n 是数组长度）；
数组中恰好有一个重复元素，且重复次数不限（至少两次）；
数组元素均为正整数（否则无法安全取负标记）；
允许临时修改原数组（因不使用额外空间，这是必要代价）。

基本实现逻辑

遍历数组，对每个元素 num，将其视为下标（注意：数组下标从 0 开始，而数值范围是 1~n，所以实际访问位置为 Math.abs(num) - 1）：

若 nums[abs(num)-1] 是正数，将其置为负数，表示“值为 abs(num) 的数已见过”；
若 nums[abs(num)-1] 已是负数，说明 abs(num) 已被标记过 → 当前 num 就是重复项，直接返回。

代码示例（单重复、返回首个重复值）

// 假设 nums 非空，且满足 [1, n] 条件

Java注释规范Skills

当用户要求为 Java 代码添加注释、修改注释、审查注释、整理注释格式，或要求按照代码注释规范处理 Java 文件时，使用本技能。本技能用于统一生成和维护 Java 类注释模板、按 Git 对比 release 判断版本号、补充每行代码上方中文块注释、调整注释空行规则，并保持 Java 文件 UTF-8 无 BOM 编码。典型触发场景包括：补充类注释、更新 @version、检查 @author 来源、整理行尾注释、把注释放到代码上一行、检查注释是否符合规范、构建前检查 Java 注释风格。

下载

public int findDuplicate(int[] nums) {
  for (int num : nums) {
    int idx = Math.abs(num) - 1;
    if (nums[idx]
      return Math.abs(num); // 重复项
    }
    nums[idx] = -nums[idx];
  }
  return -1; // 理论上不会执行到此处
}