Another solution, binary search, nlogn


  • 0
    public class Solution {
        public int findPairs(int[] nums, int k) {
            if (nums == null || nums.length == 0) return 0;
            Arrays.sort(nums);
            int ret = 0, last = Integer.MIN_VALUE;
            for (int i = nums.length - 1; i >= 1; i--) {
                if (last == nums[i]) continue;
                last = nums[i];
                int target = nums[i] - k;
                int startPos = findFirstPos(nums, target, 0, i - 1);
                if (nums[startPos] != target) continue;
                ret++;
            }
            return ret;
        }
    
        private int findFirstPos(int[] A, int target, int start, int end) {
            while (start + 1 < end) {
                int mid = start + (end - start) / 2;
                if (A[mid] >= target) {
                    end = mid;
                } else {
                    start = mid;
                }
            }
            if (A[start] >= target) return start;
            return end;
        }
    }

Log in to reply
 

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