欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
    }
}

 

相关标签: Two pointers