Check If N and Its Double Exist

Input: arr = [10,2,5,3]
Output: true
Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Input: arr = [3,1,7,11]
Output: false
Explanation: There is no i and j that satisfy the conditions.

题目 1346. “Check If N and Its Double Exist” 要求我们检查一个给定的整数数组中是否存在某个数 N 以及其值的两倍存在。换句话说，我们需要检查是否存在两个不同的索引 i 和 j，使得 arr[i] == 2 * arr[j] 或 arr[j] == 2 * arr[i]。

1. Initialization: Create a hash set to store each element of the array for quick checking whether a number or its double exists.
2. Traverse the Array: Iterate through the given integer array. For each element n, we do the following:
   • Check if the double of n or n / 2 (when n is even) exists in the hash set. If yes, return true as we have found a pair satisfying the condition.
   • Add n to the hash set for future lookup.
3. Return the Result: If we have traversed the entire array without finding any satisfying pair, then return false.
   

为什么这个代码可以满足i != j？

我们确保了i != j的条件通过以下方式得到满足：

当我们遍历数组 arr 中的每个元素时，我们检查当前元素的两倍或当前元素的一半是否已经存在于seen这个集合中。这里的关键是，在我们将当前元素添加到seen集合之前，我们会先进行检查。

这意味着，如果我们发现当前元素的两倍或一半已经在seen中，那么这两个数字一定是来自数组中的不同位置。为什么呢？因为我们还没有将当前元素加入到seen集合中，所以seen集合中的任何元素都是之前遍历过的，也就是说，它们来自当前元素的前面的数组索引。

因此，当我们在seen集合中找到当前元素的两倍或一半时，这相当于说我们找到了数组中的另一个元素（即之前遍历过的，索引比当前元素小的元素），它满足了题目中的条件，同时也确保了这两个元素（arr[i] 和 arr[j]）是不同的元素（因为它们位于数组的不同位置）。

在逻辑上，我们始终是在检查当前索引之前的元素（通过集合seen），所以当找到匹配项时，这个匹配必然来源于一个不同的索引，即满足了i != j的条件。

function checkIfExist(arr: number[]): boolean {
    const seen: Set<number> = new Set();
    for (const num of arr) {
        if (seen.has(2 * num) || (num % 2 === 0 && seen.has(num / 2))) {
            return true;
        }
        seen.add(num);
    }
    return false;

};