【Leetcode 1346 】 检查整数及其两倍数是否存在—— 哈希表 战胜了 糟糕的双指针

给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。

更正式地，检查是否存在两个下标 i 和 j 满足：

• i != j
• 0 <= i, j < arr.length
• arr[i] == 2 * arr[j]

示例 1：

输入：arr = [10,2,5,3]
输出：true
解释：N = 10 是 M = 5 的两倍，即 10 = 2 * 5 。

示例 2：

输入：arr = [7,1,14,11]
输出：true
解释：N = 14 是 M = 7 的两倍，即 14 = 2 * 7 。

示例 3：

输入：arr = [3,1,7,11]
输出：false
解释：在该情况下不存在 N 和 M 满足 N = 2 * M 。

哈希表

//哈希表
function checkIfExist2(arr: number[]): boolean {const arrMap = new Map();let ans = false;for (const n of arr) {arrMap.set(n, (arrMap.get(n) || 0) + 1);}for (const n of arr) {if ((n !== 0 && arrMap.has(2 * n)) || (n === 0 && arrMap.get(2 * n) >= 2)) {ans = true;break;}}return ans;
}

糟糕的双指针

//糟糕的双指针
function checkIfExist(arr: number[]): boolean {//排序，负数从大到小 -100 -50，正数从小到大 50 100arr = arr.sort((a, b) => (a < 0 && b < 0 ? b - a : a - b));const len = arr.length;let ans = false;//双指针let l = 0,r = Math.floor(len / 2);while (l < len - 1) {const dl = 2 * arr[l];if (arr[r] >= 0) {while (arr[r] > dl && l < r - 1) {r--;}if (arr[r] > 0) {while (arr[r] < dl && r < len - 1) {r++;}} else {while (arr[r] > dl && r < len - 1) {r++;}}} else {while (arr[r] < dl && l < r - 1) {r--;}while (arr[r] > dl && r < len - 1) {r++;}}if (arr[r] === dl) {ans = true;break;}l++;if (l === r && r + 1 < len - 1) {r++;}}return ans;
}