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