Two Sum - Unique Pairs
程序员文章站
2024-03-06 20:42:14
...
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.
Example
Example 1:
Input: nums = [1,1,2,45,46,46], target = 47
Output: 2
Explanation:
1 + 46 = 47
2 + 45 = 47
Example 2:
Input: nums = [1,1], target = 2
Output: 1
Explanation:
1 + 1 = 2
思路:同向双指针,注意去重复,i,nums[i]== nums[i-1] ,j nums[j] == nums[j+1];
public class Solution {
/**
* @param nums: an array of integer
* @param target: An integer
* @return: An integer
*/
public int twoSum6(int[] nums, int target) {
if(nums == null || nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int count = 0;
int i = 0; int j = nums.length -1;
while(i < j) {
int sum = nums[i] + nums[j];
if(sum == target) {
count++;
i++;
j--;
while(i < j && nums[i] == nums[i-1]) {
i++;
}
while(i < j && nums[j] == nums[j+1]) {
j--;
}
} else if(sum > target){
j--;
} else { // sum < target;
i++;
}
}
return count;
}
}