leetcode：442. 数组中重复的数据

题目

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 **[1, n]** 内，且每个整数出现一次或两次。请你找出所有出现两次的整数，并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

示例：

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

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

输入：nums = [1]
输出：[]

解答 & 代码

只要看到数组中的元素值在数组长度范围之内，就考虑数组元素可以作为数组的下标，数组就可以当做链表or 图 or 原地哈希表看待

原地哈希：本题数组下标范围 [0, n-1]，数组元素值范围 [1, n]，每个元素要么出现 1 次要么出现 2 次

赋予数组哈希表的含义：下标 idx 对应的元素如果是正数，说明数组中不存在元素 idx + 1；如果是负数，说明数组中存在元素 idx + 1

遍历数组，以当前元素值的绝对值 abs(nums[i]) 作为 key，查找 val = nums[key - 1]，如果 val < 0，说明这个 key 已出现过，现在是第二次出现，因此将 key 存入结果数组；否则将 nums[key - 1] 置为负数

class Solution {
public:
  vector<int> findDuplicates(vector<int>& nums) {
      vector<int> result;

      for(int i = 0; i < nums.size(); ++i)
      {
          int key = abs(nums[i]);
          int val = nums[key - 1];
          if(val < 0)
              result.push_back(key);
          else
              nums[key - 1] = -nums[key - 1];
      }
      return result;
  }
};

复杂度分析：设数组长为 N

时间复杂度 O(N)：
空间复杂度 O(1)：

执行结果：

执行结果：通过

执行用时：64 ms, 在所有 C++ 提交中击败了 19.08% 的用户
内存消耗：32.9 MB, 在所有 C++ 提交中击败了 21.38% 的用户

hot 100

[中等] 442. 数组中重复的数据

题目

解答 & 代码