检查整数及其两倍数是否存在

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 。

提示：

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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool checkIfExist(vector<int>& arr) { } };

rust 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2023-10-12 09:32:30

impl Solution {
    // 哈希 + 一次遍历
    pub fn check_if_exist(arr: Vec<i32>) -> bool {
        use std::collections::HashSet;
        let mut set = HashSet::new();

        for n in arr {
            if set.contains(&(2 * n)) || (n % 2 == 0 && set.contains(&(n / 2))) {
                return true;
            }
            set.insert(n);
        }
        false
    }
}

cpp 解法, 执行用时: 4 ms, 内存消耗: 10.7 MB, 提交时间: 2023-10-12 09:30:40

class Solution {
public:
    // 暴力枚举
    bool checkIfExist1(vector<int>& 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;
    }
    
    // 排序+双指针
    bool checkIfExist2(vector<int>& 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)
                ++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;
    }
    
    // 哈希 + 一次遍历
    bool checkIfExist(vector<int>& arr) {
        set<int> st;
        for(int a : arr){
            if((st.count(a*2))||((a&1)==0&&st.count(a/2))){
                return true;
            }
            st.insert(a);
        }
        return false;
    }
};

java 解法, 执行用时: 1 ms, 内存消耗: 41.5 MB, 提交时间: 2023-10-12 09:29:15

class Solution {
    // 哈希 + 一次遍历
    public boolean checkIfExist(int[] arr) {
        Set<Integer> set = new HashSet<>();
        for (int item : arr) {
            if (set.contains(item * 2)) {
                return true;
            }
            if (item % 2 == 0 && set.contains(item / 2)) {
                return true;
            }
            set.add(item);
        }
        return false;
    }

    // 排序 + 遍历
    public boolean checkIfExist2(int[] arr) {
        if (arr == null || arr.length == 0) return false;
        Arrays.sort(arr);
        int len = arr.length;
        int pointer = 0;
        int num = 0;
        for (int i = 0; i < len; i++) {
            num = arr[i] * 2;
            while (pointer < len && num > arr[pointer]) pointer++;
            if(pointer < len && pointer != i && num == arr[pointer]) return true;
            else if(pointer == len) break;
        }
        return false;
    }
}

python3 解法, 执行用时: 32 ms, 内存消耗: 15 MB, 提交时间: 2022-08-18 10:29:39

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        counter = collections.Counter(arr)
        for n in arr:
            if n != 0 and counter[2 * n] >= 1:
                return True
            if n == 0 and counter[2 * n] >= 2:
                return True
        return False

golang 解法, 执行用时: 8 ms, 内存消耗: 4.5 MB, 提交时间: 2021-07-02 15:08:41

func checkIfExist(arr []int) bool {
    mp := map[int]int{}
    for _, a := range arr {
        mp[a]++
    }
    for _, a := range arr {
        if a != 0 && mp[a * 2] > 0 {
            return true
        }
        if a == 0 && mp[0] > 1 {
            return true
        }
    }
    return false
}

上一题

下一题

详情