https://leetcode.cn/problems/find-all-duplicates-in-an-array
class Solution {public List<Integer> findDuplicates(int[] nums) {// 此题看似无解,但是根据数据范围,可以巧妙的使用数组本身的索引域进行标记,将索引对应的数值取负号,标记该数出现过// 等效于hash表,十分巧妙List<Integer> res = new ArrayList<>();for (int i=0;i<nums.length;i++) {int index = Math.abs(nums[i]) - 1; // 索引从0开始,nums值域[1,n] 映射到索引域 index[0~n-1]if (nums[index] < 0) {// 负数,说明此前nums[i]已经出现过res.add(Math.abs(nums[i]));} else {// 将数组索引标记,表明nums[i]这个数已经出现过nums[index] *= -1;}}return res;}
}