话不多说间接看题目
287寻找反复数：
给定一个蕴含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包含 1 和 n），可知至多存在一个反复的整数。假如只有一个反复的整数，找出这个反复的数。
示例
输出: [1,3,4,2,2]
输入: 2
输出: [3,1,3,4,2]
输入: 3
给你一个未排序的整数数组，请你找出其中没有呈现的最小的正整数。
先用hash表来解决
var fn = function(nums, target) { const map = {}; for(let i=0; i<nums.length; ++i){ if(map[nums[i]]) return nums[i] map[nums[i]] = 1 }};很简略，完满解决，还有其余形式吗
以输出[1,3,4,2,2]为例，咱们最终失去的map是
{ 1:1, 2:1, 3:1, 4:1 }能够看到这个对象的 keys 是 [1,2,3,4], 就是数组下标+1。也就是说 咱们能够把数组下标当作对象的key，来构建这个hashmap。从而把空间复杂度从 O(n) 降到 O(1)。
具体解题思路：循环，如果nums[i]!== i + 1, 把 nums[i] 放到下标为 nums[i]- 1的地位，而后把nums[i] - 1地位上本来的数 a，放到下标为a - 1,并以此循环循环，如果nums[i] === nums[nums[i] - 1]则阐明这个数呈现了两次（被搁置到正确的地位过，或者本来就存在）。文字可能说的不分明，看代码
var findDuplicate = function(nums) { for(let i = 0, len = nums.length; i < len; ++i) { // 如果以后地位不是i + 1, 进循环去换 while(nums[i] !== i + 1) { if(nums[nums[i] - 1] === nums[i]) { return nums[i] } let temp = nums[nums[i] - 1] nums[nums[i] - 1] = nums[i] nums[i] = temp } }};这样咱们应用本来的数组nums来代替map，使空间复杂度降成 O(1)。
须要留神的是，工夫复杂度并没有因为两层循环减少为 O(n^2)，因为指标语句（替换数值的局部）执行的次数仍然是n，所以工夫复杂度仍然是 O(n)。
再次重申，这道题的题目要求不能批改原数组，这种解法是不符合要求的，不过因为疏忽这个条件的话比拟适合举例。上面看一道正统的原地hash题目。
第二题
41缺失的第一个整数：
给你一个未排序的整数数组，请你找出其中没有呈现的最小的正整数。
示例
输出: [1,2,0]
输入: 3
输出: [3,4,-1,1]
输入: 2
输出: [7,8,9,11,12]
输入: 1
题目给的提醒是你的算法的工夫复杂度应为O(n)，并且只能应用常数级别的额定空间。完满合乎。
要留神的是，以[7,8,9,11,12]为例，咱们不能为了把7放到数组第(7-1)位，而扭转数组大小，因为数组length是5那么缺失的数只有可能是1-6，那么大于数组length或者小于0的数就不须要管了，置为0就能够了。代码如下。
var firstMissingPositive = function(nums) { let len = nums.length for(let i = 0; i < len; ++i) { while(nums[i] !== i + 1 && nums[i] > 0) { if(nums[nums[i] - 1] === nums[i] || nums[i] > nums.length) { nums[i] = 0 } else { let mid = nums[nums[i] - 1] nums[nums[i] - 1] = nums[i] nums[i] = mid } } } for(let i = 0; i < nums.length; ++i) { if(!(nums[i] > 0)) { return i + 1 } } return (nums[nums.length - 1] || 0) + 1};第三题
80删除排序数组中的反复项 II：
给定一个增序排列数组 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 = [0,0,1,1,1,1,2,3,3]
输入：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被批改为 0, 0, 1, 1, 2, 3, 3 。 你不须要思考数组中超出新长度前面的元素。
先说一下我一开始的思路：两个指针，一个begin指向第一个数，end向后找到第一个与begin不同的数，如果两个指针之间间隔大于2， 阐明呈现了两次以上的雷同数字，应用splice删除，而后更新begin和end的地位持续。
var removeDuplicates = function(nums) { for(let begin = end = 0; begin < nums.length; ++end) { if(nums[begin] !== nums[end]) { if(end - begin > 2) { nums.splice(begin, end - begin - 2) begin = end = begin + 2 } else { begin = end } } } return nums.length};我认为复杂度是O(n),然而疏忽了调用splice这个api自身的复杂度,如果认为splice是O(n),那么最终复杂度应该是O(n^2)。
而后就是原地hash的解法，不过这次不能单纯的用数组下标来构建了，须要借用一个指针来更新，所以还是两个指针，一个指针begin更新后果，一个指针 i 配合 i-1 向前推动。
如果nums[i] !== nums[i-1]阐明呈现了新的数字，把double置为false，更新nums[begin]
如果nums[i] === nums[i-1] 且 double=false阐明第一次呈现雷同的数字，更新nums[begin]，把double置为true，意为曾经有两个雷同的数字了，前面不必理：
var removeDuplicates = function(nums) { if(nums.length <= 2) return nums.length; var begin = 1, doubled = false; for(var i = 1; i < nums.length; i++) { if(nums[i] !== nums[i-1]) { doubled = false; nums[begin++] = nums[i]; } else if(!doubled) { doubled = true; nums[begin++] = nums[i]; } } nums.splice(begin); return begin;};