今天是一道值得用来讲的题目，来看题 LeetCode 442. 数组中重复的数据。

题目

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现一次或两次。请你找出所有出现两次的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

示例

示例 1：

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

示例 2：

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

示例 3：

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

注：题目来源于 LeetCode 442. 数组中重复的数据

题解

这道题如果不加额外条件其实很简单，但是它加了额外条件：

1	必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题

常量额外空间即O(1)，代表着我们除了用来输出输入的空间只能再加入空间固定的变量。而时间复杂度O(n)则是要求我们只能有一层循环。
那么在时间和空间都那么紧张的条件下我们能做什么呢？我们可以注意到题目中的两个条件：

nums 的所有整数都在范围 [1, n] 内
整数数组 nums 长度为 n

对于一个数组来说，它能包含的信息除了数组中的元素还有什么呢？对了，就是每个元素的下标。因为题目中nums的长度为 n 而 nums 的元素范围在 [1, n]，我们大可通过修改 下标为val 的元素的值来标志 值为val 的元素是否出现过而不影响我们使用 nums 里面的所有元素。

重申一遍， nums 的元素范围在 [1, n] 中 。我们可以通过 num[val-1]*=-1 令其成为负数标志 val 这个数已经在 nums 中出现过一次了，而我们如果需要使用 num[val-1] 则只需要使用其绝对值 abs(num[val-1]) 即可。

代码

//执行用时：40 ms, 在所有 C++ 提交中击败了84.35%的用户
//内存消耗：32.7 MB, 在所有 C++ 提交中击败了66.33%的用户
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;
        for(int i=0;i<nums.size();i++)
        {
            int num=abs(nums[i]);
            if(nums[num-1]>0)
                nums[num-1]*=-1;
            else
                ans.push_back(num);
        }
        return ans;
    }
};