前言
一般这种题型多数为数组
输出数组出现2个的个数
输出数组不是1到n的个数等等题型
一般可以使用map集合，但是复杂度偏高
是否可使用其他方式进行优化呢
进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
442. 数组中重复的数据（中等）
题目：leetcode：442. 数组中重复的数据
给你一个长度为 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]
输出：[]
提示：
n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
nums 中的每个元素出现 一次 或 两次
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer>list = new ArrayList<>();
/*
for(int num:nums){
if(nums[Math.abs(num)-1] < 0)list.add(Math.abs(num));
else nums[Math.abs(num)-1] *= -1;
}*/
/**
本身不可使用哈希表进行判断，所以通过数组的映射进行判断
本身为1-n，所以映射到数组下标为【0，n-1】
将其数组值减1 对应下标取反（主要为了标志位）
为了防止被取反后的数值（数组下标映射过来），因此每次取数组值的时候要用绝对值在减去1
如果映射的下标为负值，则说明已经被取反过一次，也就是第二次以上了
*/
for(int i = 0;i < nums.length;i++){
int ans = Math.abs(nums[i]);
if(nums[ans-1] < 0)list.add(ans);
else nums[ans-1] *=-1;
}
return list;
}
}
除了取反还有增加偏移量的操作
具体可看该题解：【负雪明烛】动画题解，原地修改数组，通俗易懂
或者使用原地转换判定，通过数组下标与对应值进行映射
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer>list =new ArrayList<>();
for(int i=0;i<nums.length;i++){
//第一个i放在合适的位置，满足的第二个i放在不冲突的位置上
while(nums[i]!=nums[nums[i]-1]){
/** 直接在这里这样写，会超时。所以写一个交换的函数即可
int temp=nums[i];
nums[i]=nums[nums[i]-1];
nums[nums[i]-1]=temp;
*/
swap(nums,i,nums[i]-1);
}
}
for(int i=0;i<nums.length;i++){
if(nums[i]-1!=i)list.add(nums[i]);
}
return list;
}
public void swap(int []nums,int a,int b){
int temp=nums[a];
nums[a]=nums[b];
nums[b]=temp;
}
}
448. 找到所有数组中消失的数字（简单）
题目：leetcode：448. 找到所有数组中消失的数字
大致意思如下：
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例 1：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]
示例 2：
输入：nums = [1,1]
输出：[2]
提示：
n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer>list =new ArrayList<>();
for(int i=0;i<nums.length;i++){
while(nums[i]!=nums[nums[i]-1]){
swap(nums,i,nums[i]-1);
}
}
for(int i=0;i<nums.length;i++){
/**
此题 跟其他题不一样的区别在于 寻找的是消失的数字
所以下标对应的是出现重复的数字，对此 消失的数字应该是下标值加1的值
*/
if(nums[i]-1!=i)list.add(i+1);
}
return list;
}
//此处为置换排序，根本的思想其实就是nums[nums[i]]==nums[i]
public void swap(int []nums,int a,int b){
int temp=nums[a];
nums[a]=nums[b];
nums[b]=temp;
}
}
使用取反的操作，具体代码如下：
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer>list =new ArrayList<>();
for(int i=0;i<nums.length;i++){
int ans=Math.abs(nums[i]);
if(nums[ans-1]>0)nums[ans-1] *=-1;
}
for(int i=0;i<nums.length;i++){
if(nums[i]>0)list.add(i+1);
}
return list;
}
}
剑指 Offer 03. 数组中重复的数字（简单）
题目：leetcode：剑指 Offer 03. 数组中重复的数字
大致意思如下：
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
class Solution {
public int findRepeatNumber(int[] nums) {
for(int i=0;i<nums.length;i++){
//本身数组的下标和 对应的值 都是0到n-1.
while(nums[i]!=nums[nums[i]]){
swap(nums,i,nums[i]);
}
}
for(int i=0;i<nums.length;i++){
if(nums[i]!=i)return nums[i];
}
return -1;
}
//此处为置换排序，根本的思想其实就是nums[nums[i]]==nums[i]
public void swap(int []nums,int a,int b){
int temp=nums[a];
nums[a]=nums[b];
nums[b]=temp;
}
}
