题目:
给你一个长度为 n 的整数数组 nums ,其中 nums 的所有整数都在范围 [1, n] 内,且每个整数出现 最多两次 。请你找出所有出现 两次 的整数,并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间(不包括存储输出所需的空间)的算法解决此问题。
示例 1:
输入:nums = [4,3,2,7,8,2,3,1]
输出:[2,3]
示例 2:
输入:nums = [1,1,2]
输出:[1]
示例 3:
输入:nums = [1]
输出:[]
解析:
这道题的思想是原地哈希,因为题目中比较特殊,数组中每一个数的值是在[1,n]这个区间中,数组的长度也刚好为n,所以我们可以借助数组中某个数的前一个索引表示这个数是否出现过,如果没出现过,就将这个数减一作为下标对应的元素设置为负数。
举个例子:
比如数组有个元素为4,那么我们将arr[4-1]对应的那个元素乘以-1,变为负数,那么下次我们再次遇到4这个数的时候,我们去查看arr[4-1]对应的元素,如果对应的元素为负数,那么说明元素4之前出现过一次
具体代码:
/** * 找出数组中所有出现两次的元素(LeetCode 442题) * 条件:1 ≤ nums[i] ≤ n,n为数组长度,每个元素最多出现两次 * @param {number[]} nums - 输入数组,元素值在[1, n]范围内 * @return {number[]} - 返回所有出现两次的元素 */varfindDuplicates=function(nums){// 存储结果的数组letres=[]// 遍历数组中的每个元素for(leti=0;i<nums.length;i++){// 取当前元素的绝对值(因为可能已经被标记为负数)letk=Math.abs(nums[i])// 检查 nums[k-1] 这个位置的值:// - 如果 nums[k-1] > 0:说明数字 k 是第一次出现// - 如果 nums[k-1] < 0:说明数字 k 之前已经出现过一次,现在是第二次出现// 核心思路:用索引 (k-1) 位置的符号来标记数字 k 是否出现过if(nums[k-1]>0){// 第一次遇到数字 k:将 nums[k-1] 标记为负数// 负号作为"已访问"标记,不影响我们通过 Math.abs 获取原始值nums[k-1]*=-1}else{// 第二次遇到数字 k:当前 nums[k-1] 已经是负数// 说明 k 是重复元素,将其加入结果数组res.push(k)}}// 返回所有出现两次的元素returnres};