Java sort and binary search solution, 28ms with explanation

• The basic idea is to sort the array and skip the duplicate pairs so we only need iterating the array once. And for a given value at nums[i], we only need to find if nums[i]+k exists in the subarray of range [i+1,end]. We can use binary search for each iteration, thus the time complexity is O(nlogn).

``````	public int findPairs(int[] nums, int k) {
Arrays.sort(nums);
int count = 0;
int prev = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != prev) {
if (binary_search_pair(nums, nums[i] + k, i + 1, nums.length - 1))
count++;
prev = nums[i];
}
}
return count;
}

private boolean binary_search_pair(int nums[], int t, int st, int ed) {
if (st > ed)
return false;
int mid = (st + ed) / 2;
if (nums[mid] < t)
return binary_search_pair(nums, t, mid + 1, ed);
else if (nums[mid] > t)
return binary_search_pair(nums, t, st, mid - 1);
else
return true;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.