解題 25. Check If N and Its Double Exist (3 行解法)

25 1 月, 2022 欣迪

Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).

More formally check if there exists two indices i and j such that :

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

Example 1:

Input: arr = [10,2,5,3]
Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.

Example 2:

Input: arr = [7,1,14,11]
Output: true
Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.

Example 3:

Input: arr = [3,1,7,11]
Output: false
Explanation: In this case does not exist N and M, such that N = 2 * M.

Constraints:

2 <= arr.length <= 500
-10^3 <= arr[i] <= 10^3

這題是在找，陣列內是否有任一數為另一個數字的兩倍。

先附上一開始的寫法，很單純的用一個廻圈逐個測試陣列內是否有當前數值兩倍的數。

var checkIfExist = function(arr) {
    return arr.some((item) => {
        return arr.indexOf(item * 2) >= 0
    })
};

喔喔！報錯了！

很顯然這樣的做法，並沒有把 0 考慮進去。上面的做法直接去偵測全部陣列的內容是否為當前數值的兩倍，所以當出現 0 時，因為 0 * 2 還是 0 所以會把自身的這個 value 當成是符合條件，給了一個 true 的錯誤答案。

為了避免這樣的錯誤，所以必須要排除自身可能為 0 的狀態。所以使用了該數值的索引來排除找到自己。

var checkIfExist = function(arr) {
    return arr.some((item, idx) => {
        const targetIdx = arr.indexOf(item * 2)
        return targetIdx >= 0 && targetIdx !== idx
    })
};

這個做法可以 pass ，但是由於 indexOf 方法，會回傳第一個發現符合條件的位置，當遇到陣列內有兩個 0 的狀態出現時，會回傳第一個 0 的位置，因此，會一直到第二個 0 出現時才跑出正確的解答。

Array.prototype.lastIndexOf

如果使用 lastIndexOf 則可避免這個情形，從 array 的結尾往前找符合的條件。這樣如果遇到 0 ，就可以在第一次出現就取得正確答案。

var checkIfExist = function(arr) {
    return arr.some((item, idx) => {
        const targetIdx = arr.lastIndexOf(item * 2)
        return targetIdx >= 0 && targetIdx !== idx
    })
};

IT僧