个人认为很好的一道面试题
虽然题目简单但如果直接暴搜的话应该就直接回家等通知了
有好几种做法面试的时候都可以说一下

法1: 二分

排序后 遍历数组 二分查找是否存在二倍的值
复杂度:
排序 nlogn 二分 n * logn
O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from typing import List
from bisect import *


class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        arr.sort()
        n = len(arr)
        for i in range(n):
            v = arr[i]
            index = bisect_left(arr,2*v)
            if index >= n or index == i:
                continue
            if 2*v == arr[index]:
                return True

        return False

法2: 哈希

遍历一遍将所有值都加到hash中
再遍历一遍 同时在hash中寻找结果
复杂度: 可做到近乎O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        s = set()
        # 判断0的个数 防止只有一个0的情况出现
        zeroCount = 0
        for v in arr:
            if not v:
                zeroCount = zeroCount + 1
            s.add(v)

        for v in arr:
            # 特判0 的情况
            if not v:
                if zeroCount > 1:
                    return True
            elif 2*v in s:
                return True
        return False

法3 排序 双指针

这个做法的核心在于单调性的应用
以x>0 为例:
对于排序后的数组
arr[i] * 2 > arr[p]
p = p + 1
即 i-p 之间均是小于arr[i] * 2 的数 因为数组本身单调增的 所以如果 i继续向右至j 那么原本 i-p 之间的数必然小于 arr[j] * 2 即p 只需遍历一次即可

复杂度:
排序 nlogn 遍历 2 * n
总的复杂度 O(nlogn)
不过这种方法相对来说还是复杂了一些 而且判断需要注意的细节也比较多 还是不建议写 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        n = len(arr)
        arr.sort()
        p = 0
        # 判断x 大于0的情况 
        # 对于排序后的数 arr[i]*2 > arr[p]  p = p + 1
        for i in range(n):
            while p < n and arr[i] * 2 > arr[p]:
                p = p + 1
            if p < n and p!=i and arr[i] * 2 == arr[p]:
                return True
        
        p = n - 1
        # 判断小于0的情况
        # 对于排序后的数 arr[i]*2 < arr[p]  p = p -1
        # 否则无法达成两倍这个条件 因为你负的数越往左才是越小其绝对值才是越大 
        # 同时i 逆着遍历 才能满足单调性一致 即p 不需要回溯
        for i in range(n-1,-1,-1):
            while p > -1 and arr[i]*2 < arr[p]:
                p = p -1
            if p > -1 and p!=i and arr[i] * 2 == arr[p]:
                return True
        
        return False