Java one pass AC O(n) time O(1) space solution for a sorted array 20ms Beats 95%


  • 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 < nums.length - 1 && right < nums.length) {
                if (left > 0 && nums[left] == nums[left - 1]) {
                    left++; // remove duplicates
                }
                else if (nums[right] - nums[left] < k) {
                    right++;
                } else if (nums[right] - nums[left] == k) {
                    count++;
                    left++;
                } else {
                    left++;
                }
                if (left == right) {
                    right++;
                }
            }
            return count;
        }
    }
    

Log in to reply
 

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