1.存在重复元素（217 - 易）
题目描述：给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 :
输入: [1,2,3,1] 输出: true
思路：
- 本题可以先排序再遍历数组，简单。
- 也可以利用HashSet去重判断，依次计入集合。
代码实现：hashset
public boolean containsDuplicate(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums) { set.add(num); } return set.size() < nums.length; }
2.剑指 Offer 03. 数组中重复的数字
题目描述：找出数组中重复的数字（含有多个重复元素）。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 :
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3
思路：
- 使用hashset，当元素王集合中加入失败
if (!set.add(num))，即存在重复元素，返回即可（返回任意重复元素）。 - 原地置换（快慢指针）：根据题目元素都小于长度n，可以让 位置i 的地方放元素i（有重复数字，索引和值是一对多映射）。
- 如果位置i的元素不是i的话，那么我们就把i元素放到它应该在的位置，即 nums[i] 和nums[nums[i]]的元素交换（即元素nums[i]应该放在下标nums[i]），这样就把原来在nums[i]位置的元素正确归位了。
- 如果发现 要把 nums[i]位置元素正确归位的时候，发现nums[i]（这个nums[i]是下标）那个位置上的元素和要归位的元素已经一样了，此时一定nums[i] == nums[nums[i]]，说明就重复了
- 值域的二分查找：数组元素值介于 0～n-1，且至少存在一个元素是重复的。可以对值域进行二分查找，统计nums数组中元素介于0mid的数量，如果这个数量大于mid值，重复元素肯定在0m之间。
ps：二分查找没有ac，请教大佬指点！
代码实现：hashset实现：额外空间复杂度O(N)，不修改原始数据。
public int findRepeatNumber(int[] nums) { Set<Integer> set = new HashSet<Integer>(); int repeat = -1; for (int num : nums) { // 集合中已经存在该元素 if (!set.add(num)) { repeat = num; break; } } return repeat; }
快慢指针（原地置换）：不使用额外空间，原地查找，时间复杂度O(N)，但修改了原始数据。
public int findRepeatNumber(int[] nums) { int tmp; for(int i = 0; i < nums.length; i++){ while (nums[i] != i){ if(nums[i] == nums[nums[i]]){ return nums[i]; } // 将元素nums[i]归位（放到下标为nums[i]位置） tmp = nums[i]; nums[i] = nums[tmp]; nums[tmp] = tmp; } } return -1; }
3.寻找重复数（287 - 中）
题目描述：给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
示例 :
输入：nums = [1,3,4,2,2] 输出：2
思路：
- 使用hashset，当元素王集合中加入失败
if (!set.add(num))，即存在重复元素，返回即可（返回任意重复元素）。 - 快慢指针（最优解），因为元素介于1~n，且只存在一个重复值，所以可以看成链表找环的入口，使用快慢指针查找，快指针一次跳两步（不会出现数组越界）。
- 二分查找：虽然数组无序，但是值域1~n，可以在值域上进行二分查找。
代码实现：
hashset实现：额外空间复杂度O(N)，不修改原始数据。
public int findDuplicate(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums) { if (!set.add(num)) return num; set.add(num); } return -1; }
快慢指针：不使用额外空间，原地查找，时间复杂度O(N)，但修改了原始数据。
public int findDuplicate(int[] nums) { int l1 = 0, l2 = 0; while (true) { l1 = nums[l1]; l2 = nums[nums[l2]]; if (l1 == l2) break; } l2 = 0; while (l1 != l2) { l1 = nums[l1]; l2 = nums[l2]; } return l1; }
值域的二分查找：时间O(NlongN)，额外空间复杂度O(1)，不修改原数据。
public int findDuplicate(int[] nums) { int l = 1, r = nums.length - 1; while (l < r) { int mid = l + ((r - l) >> 1); int cnt = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] <= mid) { cnt++; //记录小于等于mid元素的个数 } } if (cnt > mid) { //重复值在左区域，mid取大了 r = mid; } else { l = mid + 1; //重复值在右区域，mid取小了 } } return l; }
4.补充：快乐数（202 - 易）
题目描述：编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例 :
输入：19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
思路：快慢指针，每个数字都会根据 各位平方和 指向另一个数字，从任意数字开始进行 各位平方和 的迭代操作，就相当于在链表上游走。如果快指针找到则提前退出。如果快慢指针相遇，那么必定出现循环（存在环，死循环），需要判断这个循环值是不是1。
代码实现：
public int squareSum(int n) { int sum = 0; while(n > 0){ int digit = n % 10; sum += digit * digit; n /= 10; } return sum; } public boolean isHappy(int n) { int slow = n, fast = squareSum(n); while (fast != 1 && slow != fast){ slow = squareSum(slow); fast = squareSum(squareSum(fast)); } return fast == 1; }
5.删除有序数组中的重复项（26 - 易）
题目描述：给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 :
输入：nums = [1,1,2] 输出：2, nums = [1,2] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
思路：快慢指针，快指针遍历数组，慢指针记录不重复的元素（遇到与慢指针元素不同，将快指针指向元素覆盖慢指针指向元素），最后返回慢指针下标 + 1，即为删除后数组长度。
代码实现：快慢指针，不使用额外空间，原地查找，时间复杂度O(N)。
public int removeDuplicates(int[] nums) { int slow = 0; for (int fast = 1; fast < nums.length; fast++) { if (nums[fast] != nums[slow]) { nums[++slow] = nums[fast]; } } return slow + 1; }
6.删除有序数组中的重复项II（80 - 中）
题目描述：给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素最多出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 :
输入：nums = [1,1,1,2,2,3] 输出：5, nums = [1,1,2,2,3] 解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
思路：快慢指针，快指针遍历数组，慢指针记录不重复的元素，注意：这里快指针指向元素依次比较元素nums[slow - max + 1]，即上一轮已经覆盖完成的两个元素，这里max需要返回元素的最多重复数。
代码实现：快慢指针，不使用额外空间，原地查找，时间复杂度O(N)。
public int removeDuplicates(int[] nums) { int slow = 1; int max = 2; // 返回元素的最多重复次数 for (int fast = 2; fast < nums.length; fast++) { if (nums[slow - max + 1] != nums[fast]) { nums[++slow] = nums[fast]; } } return slow + 1; }
