Java two pointer solution beats 97%


  • 1
    T

    The idea is simple. Sort the array first. Then for each number in the array, find if there exists a number satisfy the requirement. Note that right = Math.max(right, i + 1) can make sure each number in the array is accessed at most twice. So the time complexity is O(nlogn) + O(n) = O(nlogn)

    public int findPairs(int[] nums, int k) {
        if (nums.length < 2 || k < 0) {
            return 0;
        }
        int count = 0;
        Arrays.sort(nums);
        int right = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
                
            right = Math.max(right, i + 1);
            while (right < nums.length) {
                if (nums[right] - k == nums[i]) {
                    count++;
                    break;
                } else if (nums[right] - k < nums[i]) {
                    right++;
                } else {
                    break;
                }
            }
        }
        return count;
    }
    

Log in to reply
 

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