Leetcode 1346. Check whether integers and their multiples exist

1346、 Check the existence of integers and their multiples

1） Title Description

Give you an array of integers arr, Please check whether there are two integers N and M, Satisfy N yes M Twice as many （ namely ,N = 2 * M）.

More formally , Check if there are two subscripts i and j Satisfy ：

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

Example 1：

 Input ：arr = [10,2,5,3]
 Output ：true
 explain ：N = 10  yes  M = 5  Twice as many , namely  10 = 2 * 5 .

Example 2：

 Input ：arr = [7,1,14,11]
 Output ：true
 explain ：N = 14  yes  M = 7  Twice as many , namely  14 = 2 * 7 .

Example 3：

 Input ：arr = [3,1,7,11]
 Output ：false
 explain ： Does not exist in this case  N  and  M  Satisfy  N = 2 * M .

Tips ：

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

2） analysis

Sort , Two points search .

• Sort the array first ;
• Then, by bisection, we can find whether there is an element in the array equal to twice the current element , In binary search , for fear of 0 Make a mistake , To exclude the current element itself .

3）C++ Code

class Solution {
    
public:
    bool checkIfExist(vector<int>& arr) {
    
        sort(arr.begin(),arr.end());
        for(int i=0;i<arr.size();i++){
    
            int left=0;
            int right=arr.size()-1;
            while(left<=right){
    
                int mid=(left+right)/2;
                if(arr[mid]==2*arr[i]&&i!=mid)
                    return true;
                else if(arr[mid]<2*arr[i])
                    left=mid+1;
                else
                    right=mid-1;
            }
        }
        return false;
    }
};