Leetcode - Check If N and Its Double Exist

violet posted @ Apr 02, 2020 06:24:40 AM in 算法 with tags Algorithm Golang hash array , 538 阅读

https://leetcode.com/problems/check-if-n-and-its-double-exist/

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]

Time complexity: O(n)

func checkIfExist(arr []int) bool {
    hash := map[int]bool{}
    count0 := 0
    for i := 0; i < len(arr); i++ {
        if arr[i] == 0 {
            count0++
        }
        hash[arr[i]*2] = true
    }
    if count0 > 1 {
        return true
    }
    for i := 0; i < len(arr); i++ {
        if hash[arr[i]] && arr[i] != 0 {
            return true
        }
    }
    
    return false
}