Thursday, March 30, 2017

Two Sum - Unique pairs

Given an array of integers, find how many unique pairs in the array such that their sum is equal to a specific target number. Please return the number of pairs.
First of all, if we want to use the two pointers method, we must make sure that the array is sorted.
Second, we can not remove duplicates before head since it is possible that two equal numbers might add up to the target.
So we always choose the 1st number we meet as the representative of the number. If the current number equals to its previous number, we need to move on.

public class Solution {
    /**
     * @param nums an array of integer
     * @param target an integer
     * @return an integer
     */
    public int twoSum6(int[] nums, int target) {
        // Write your code here
        int count = 0;
        if (nums == null || nums.length <= 1) return count;
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        //we fix left pointer and look for the right pointer
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                count++;
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) left++;
                while (left < right && nums[right] == nums[right + 1]) right--;
            } else if (nums[left] + nums[right] > target) {
                right--;
            } else {
                left++;
            }
        }
        return count;
    }
}

No comments:

Post a Comment