動機
注意正負數的2倍,分別會變大變小
Problem
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 :
- t
i != j
t0 <= i, j < arr.length
tarr[i] == 2 * arr[j]
Example 1:
Input: arr = [10,2,5,3]Output: trueExplanation: N= 10
is the double of M= 5
,that is,10 = 2 * 5
.
Example 2:
Input: arr = [7,1,14,11]Output: trueExplanation: N= 14
is the double of M= 7
,that is,14 = 2 * 7
.
Example 3:
Input: arr = [3,1,7,11]Output: falseExplanation: In this case does not exist N and M, such that N = 2 * M.
Constraints:
- t
2 <= arr.length <= 500
t-10^3 <= arr[i] <= 10^3
Sol
class Solution {
public:
bool checkIfExist(vector<int>& arr) {
sort(arr.begin(),arr.end());
for(auto i=arr.begin();i!=arr.end();i++) {
int target = (*i < 0) && ((*i) % 2 == 0) ? (*i)/2 : (*i)*2;
auto j = lower_bound(i+1,arr.end(),target);
if (j != arr.end() && *j == target) {
cout << *i << ',' << *j << '\n';
return 1;
}
}
return 0;
}
};