后面3个题都是限制在1～n的，所有可以不先排序，可以利用巧方法做。最后两个题几乎一模一样。
217. Contains Duplicate
可以通过排序然后判断相邻两个的数是否相等，时间复杂度O(nlogn),空间复杂度O(1)
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
int length = nums.size();
if(length <= )
return false;
sort(nums.begin(),nums.end());
for(int i = ;i < length;i++){
if(nums[i] == nums[i-])
return true;
}
return false;
}
};使用hash-map，时间复杂度时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_map<int,int> m;
for(int i = ;i < nums.size();i++){
if(m.count(nums[i]) == )
m[nums[i]] = ;
else
return true;
}
return false;
}
};219. Contains Duplicate II
有没有重复的两个数，且这两个数的之间的距离大于k
用hash存储数和index，如果大于了k，就以当前这个位置的index重新更新数所对应的位置索引
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int,int> m;
for(int i = ;i < nums.size();i++){
if(m.count(nums[i]) == )
m[nums[i]] = i;
else
if(i - m[nums[i]] > k)
m[nums[i]] = i;
else
return true;
}
return false;
}
};220. Contains Duplicate III
http://www.cnblogs.com/grandyang/p/4545261.html
要求两数的索引的绝对值小于k，数值差的绝对值小于t。
索引的绝对值小于k可以用一个滑动窗口来解决，即代码中的j是窗口的左边界，i是当前窗口右边界，一旦超过了k就移动左边界。
数值差的绝对值小于t相当于：|Ni - Nj| <= t，展开得到-t <= Ni - Nj <= t，继续变换得到Nj-t <= Ni <= Nj+t,最终得到Ni - t <= Nj <= Ni + t。
lower_bound是寻找第一个大于等于当前数的结果，也就是说找第一个满足下边界的Nj，lower_bound返回的是一个迭代器，如果能找到下边界的第一个，并且满足上边界就证明可以找到这么一个值。如果找到，但是不满足上边界，那证明当前的map中没有数可以满足上边界，因为这个数是最小的下边界数，不满足上边界则代表大于上边界，既然这个最小的都大于上边界，其他数也都大于上边界。这里的代码实际上是想实现判断是否满足上边界，只是写成了abs的形式。
map, set等数据结构是基于红黑树实现的，unordered_map和unordered_set是基于哈希表实现的，而stack和priority_queue分别是栈和堆，能用lower_bound的数据结构是map, set, 或者vector这样的容器。首先我们要知道lower_bound的实现是基于二分搜索法的，那么容器必须要有序，所以那些unordered什么的自然不能用了。
时间复杂度为nlogn，lower_bound时间复杂度为logn
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
map<long,int> m;
int j = ;
for(int i = ;i < nums.size();i++){
if(i - j > k)
m.erase(nums[j++]);
auto it = m.lower_bound((long)nums[i] - t);
if(it != m.end() && abs(nums[i] - it->first) <= t)
return true;
m[nums[i]] = i;
}
return false;
}
};287. Find the Duplicate Number
注意:这个mid是数字，不是下标。
假设一个没有重复的数组是[1,2,3,4]
没有重复的话，小于等于2的个数应该是2个，小于等于3的个数是3个。
对于一个有重复的数组[1,2,2,3,4]
小于等于2的个数是3，小于等于3的个数是4，也就是说超过了他本身的值了。
用二分法，找中间值，如果超过了本身的数，说明重复的数一定小于他本身；没有超过，说明重复的数一定大于他本身
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int length = nums.size();
if(length <= )
return -;
int start = ;
int end = length - ;
while(start < end){
int mid = (start + end)/;
int count = ;
for(int i = ;i < length;i++){
if(nums[i] <= mid)
count++;
}
if(count > mid)
end = mid;
else
start = mid + ;
}
return start;
}
};http://www.cnblogs.com/grandyang/p/4843654.html
https://blog.csdn.net/xudli/article/details/48802345
https://segmentfault.com/a/1190000003817671
442. Find All Duplicates in an Array
注意比的时候要i+1，因为数值比坐标大
把数放到他对应的索引下重新排数组，排完后统计那些索引不等于自己的值的结果
这个i--其实就是表明了一直在这个位置循环直到找到值和索引相同的
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> result;
int length = nums.size();
if(length <= )
return result;
for(int i = ;i < length;i++){
if(nums[i] != nums[nums[i] - ]){
swap(nums[i],nums[nums[i]-]);
i--;
}
}
for(int i = ;i < length;i++){
if(nums[i] != i + )
result.push_back(nums[i]);
}
return result;
}
};http://www.cnblogs.com/grandyang/p/6209746.html
448. Find All Numbers Disappeared in an Array
这个题与442的题代码几乎一模一样，只是result存储的是坐标+1，也就是具体的消失的数值
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> result;
int length = nums.size();
for(int i = ;i < length;i++){
if(nums[i] != nums[nums[i]-]){
swap(nums[i],nums[nums[i]-]);
i--;
}
}
for(int i = ;i < length;i++){
if(nums[i] != i+)
result.push_back(i+);
}
return result;
}
};https://www.cnblogs.com/grandyang/p/6222149.html