AC Java two pointer solution O(n) beats 94%


  • 0
    H
    public class Solution {
        public int findPairs(int[] nums, int k) {
            if (nums == null || nums.length < 2) {
                return 0;
            }
            
            Arrays.sort(nums);
            
            int count = 0;
            int left = 0, right = 1;
            while (left < right && right < nums.length) {
                if (nums[right] - nums[left] < k) {
                    right++;
                } else if (nums[right] - nums[left] == k) {
                    count++;
                    left++;
                    right++;
                    //skip duplicates 
                    while (left < nums.length && nums[left] == nums[left - 1]) {
                        left++;
                    }
                } else {
                    left++;
                }
                //make sure the left < right
                while(right < nums.length && right <= left) {
                    right++;
                }
            }
            return count;
        }
    }
    

Log in to reply
 

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