哈希|Leetcode二分查找11:1346. 检查整数及其两倍数是否存在算法|leetcode|数据结构|c++

链接：https://leetcode-cn.com/problems/check-if-n-and-its-double-exist/
文章图片
https://leetcode-cn.com/problems/check-if-n-and-its-double-exist/
题意就在题目中。
一.初步分析初看题目可以暴力解，二重循环解决。
时间复杂度：O(n^2)
空间复杂度：O(1)

class Solution { public: bool checkIfExist(vector& arr) { for (auto i = arr.begin(); i != arr.end(); ++i) for (auto j = arr.begin(); j != arr.end(); ++j) if (i != j && *i * 2 == *j) return true; return false; } };

二.对暴力进行优化首先想到二分、双指针。
但是这样开始也必须排序，然后定义两个指针：指针p遍历x，指针q找2x。分为两种情况：
1.对于 x>0 的情况，指针只需要一直前进。若q在前进过程中找到一个比 2x大的数字，那么2x必然不存在(数组元素已经升序排列)。在p前进的过程中p所指向的x会不断递增，2x也会不断递增，因此指针q不需要后退。
2.对于 x<0 的情况，指针只需要一直后退。若q在后退过程中找到一个比2x小的数字，那么2x必然不存在(数组元素已经升序排列)。在p后退的过程中p所指向的x会不断递减，2x也会不断递减，因此指针q不需要前进。
时间复杂度：O(nlogn)
排序的时间复杂度为O(nlogn)，两次指针遍历的过程时间复杂度为O(n)，综合起来，复杂度为 O(nlogn)。
空间复杂度：O(n)
sort 函数空间复杂度为 O(n)，双指针遍历的空间复杂度为 O(1)，综合起来，复杂度为 O(n)。

class Solution { public: bool checkIfExist(vector& arr) { sort(arr.begin(), arr.end()); for (auto i = arr.begin(), j = arr.begin(); i != arr.end(); ++i) {//从前向后 while (j != arr.end() && *i * 2 > *j)//必须写成*i(像指针一样),且j在i后，肯定是i*2==j ++j; if (j != arr.end() && i != j && *i * 2 == *j) return true; } for (auto i = arr.rbegin(), j = arr.rbegin(); i != arr.rend(); ++i) {//从后往前 while (j != arr.rend() && *i * 2 < *j) ++j; if (j != arr.rend() && i != j && *i * 2 == *j) return true; } return false; } };

三:神级方法:哈希哈希法适用于数组值与下标之间相互查找，用一个auto类型的变量x去遍历数组arr，如果m[2*x]或者m[x/2](x为偶数)存在，返回true；如果遍历的值不存在那么m[x]就自增，继续查找。
时间复杂度：O(n)
哈希表的查询时间复杂度为O(1)，查询次数为O(n)，综合起来，时间复杂度为O(n)。
空间复杂度：O(n)
哈希表最多需要存储n个元素。

class Solution { public: bool checkIfExist(vector& arr) { unordered_map m; for(auto x:arr){ if(m[x*2]||(m[x/2]&&x%2==0)) return true; else m[x]++; } return false; } };