Java Solution, no extra space, sort+binary search


  • 0
    D
    public static int findPairs(int[] nums, int k) {
            if(nums==null || nums.length<=0 || k<0){
        		return 0;
        	}
            //sort
        	Arrays.sort(nums);
        	//traverse array and use binary search the k-diff elements after i
        	int cnt=0;
        	for(int i=0;i<nums.length-1;i++){
        		if(Arrays.binarySearch(nums, i+1, nums.length, nums[i]+k)>=0){
        			cnt++;
        		}
                    // deal with duplications
        		while(i<nums.length-1 && nums[i] == nums[i+1]){
        			i++;
        		}
        	}
        	return cnt;
        }
    

Log in to reply
 

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