这两道题题目基本一样，只不过一个只需要找到一个，一个需要找到所有的数字，难度稍稍大了一点，废话不多说直接上题。
题目一
这道题其实还是比较简单的，而且解决方法也很多样，这里我会列举几种常用的方法，并讲解一种比较巧妙的方法。
核心思想
-
暴力法
既然要找重复的数字，那最直接的方法就是遍历每个元素，然后对每个元素向后继续遍历剩下的元素，找到重复的直接返回即可。时间复杂度O(N²) -
集合法
我们可以使用一个集合(或者定义一个大数组，下标对应给定数组元素的值，然后0表示没有这个数，1表示出现过这个数即可)HashSet，然后遍历数组向集合中加入元素，如果contains的话返回即可。时间复杂度O(N)，空间复杂度O(N) -
排序法
既然要寻找重复元素，直接将数组排序，然后找到 nums[i] == nums[i + 1]直接返回即可。时间复杂度O(nlogn) 不过Java的快排在实际使用时效率可能会优于维护HashSet。
这些就是比较常见而且容易想到的方法，接下来的方法可能不是很容易想到，是在集合法的基础上进行优化，由于集合法需要额外的O(N)的空间，可以对此进行优化。至于优化的方法，就是使用题目给的 nums数组，从而不需要使用额外的空间。因为题目给出了数组里的数字都限定在 0 — n - 1之间，那么我们可以让数字i 就存放在数组的 nums[i] 的位置上，详见代码。
完整代码
class Solution {
public int findRepeatNumber(int[] nums) {
for(int i = 0; i < nums.length; i++){
while(nums[i] != i){
if(nums[i] == nums[nums[i]]){
//想要交换的数组元素重复
return nums[i];
}
int temp = nums[i];//备份nums[i];
nums[i] = nums[temp];//交换nums[nums[i]] 和nums[i]
nums[temp] = temp;
}
}
return -1;
}
}
对于每一个下标 i 都判断他的位置是否放了正确的数字 i ，是的话直接判断下一个下标，不是的话将nums[i] 交换到正确的位置然后依次循环，而如果他想要交换的元素已经出现过并且在正确位置了，就代表出现了重复，直接返回即可。时间复杂度O(N) 虽然使用了两层循环，但是依然是每个元素只访问一次，正确位置或者交换过到了正确位置的会直接跳过。 空间复杂度O(1) 除了题目给出的nums数组，没有使用额外的空间，是一个优解。
题目二
核心思路
这道题跟上一题十分相似，但是细节上差了不少，这道题的数组限制元素的范围在1-n，也就是说还可以按上一题的交换方法，使得1在0处，2在1处……即可；再一个重复元素只会出现两次，并且要返回所有的重复元素，方法同样可以有多种，暴力、排序、集合都可以解决。不过题干给出一句“你可以不用到任何额外空间并在O(N)时间复杂度内解决这个问题吗？”，发现这个要求很苛刻，上边的三种方法都不能实现，而第一题的方法使用过了就不再赘述，我们尝试换一种方法，那该怎么解决呢？根据上一题的思路，我们需要在集合法的基础上将集合和给定的nums数组融到一起，以达到O(N)时间及无额外空间的要求。可以注意到题干给出的加粗字 两次 ，两次就是在引到我们到：-（-1）= 1，也就是说，我们仍然可以用数组的下标来代表元素，只不过这次我们不再用值，而是用符号，根据元素的范围，数组元素都是正整数，那只要对出现过的元素对应下标的元素符号改为 ‘-’ 就可以不使用额外的空间来解决问题。
完整代码
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<Integer> findDuplicates(int[] nums) {
ArrayList<Integer> ans = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
if (nums[Math.abs(nums[i]) - 1] < 0) {
ans.add(Math.abs(nums[i]));
} else {
nums[Math.abs(nums[i]) - 1] *= -1;
}
}
return ans;
}
}
如果数字nums[i] 出现过，那么它对应的下标元素 nums[nums[i]]就应该小于0，从而找到重复的元素。须要注意的是，因为当前遍历的nums[i]元素可能在之前被置为 -nums[i] 所以访问的时候要注意使用绝对值，不然会超出下标界限报错。这种方法还是很巧妙的，当然用上一题的交换方法也是可以AC的，看个人选择即可。
