Given an int array nums and an int target, find how many unique pairs in the array such that their sum is equal to target. Return the number of pairs.

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
Example 3:
Input: nums = [1, 5, 1, 5], target = 6
Output: 1
Explanation:
[1, 5] and [5, 1] are considered the same.

import java.util.*;

public class TwoSum2 {
    public static void main(String[] args) {
        int[] arr1 = {1,2,45,46,46};
        int target1 = 47;
        System.out.println(twoSumPairs(arr1, target1));

        int[] arr2 = {1,1,1,1,1,1,1,1};
        int target2 = 2;
        System.out.println(twoSumPairs(arr2, target2));

        int[] arr3 = {1,5,1,3,3,3,3,3,5};
        int target3 = 6;
        System.out.println(twoSumPairs(arr3, target3));
    }

    //one set
    //time complexity O(nlogn)
    //space complexity O(n)
    public static int twoSumPairs(int[] nums, int target) {
        Set<Integer> set = new HashSet<>();
        int count = 0;
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++) {
            if(!set.contains(target - nums[i])) {
                set.add(nums[i]);   //set中没有target - nums[i]时，把nums[i]加入set
            }
            else {    //set中有target - nums[i]时，表明当前值可与该值形成一个和为target的配对，那这一对能不能放进结果里面要考虑几种情况
                if(i > 0 && nums[i] != nums[i - 1]) {  // 解决【1，46，46】47 的情况，46 can only be counted once, so when the current number equal to previous number, it can't be counted again
                    count++;
                }
                if(nums[i] == target - nums[i] && (i - 2 < 0 || nums[i - 2] != nums[i])) { //解决【1，2，2，2】4 的情况 the first 2,2 pair is not count in previous if, but this should be count, and only this should be count
                    count++;
                }
            }
        }
        return count;

    }

    //two sets
    //time complexity O(n)
    //space complexity O(2n)
//    public static int twoSumPairs(int[] nums, int target) {
//        Set<Integer> set = new HashSet<>();   //store all unique numbers during iteration
//        Set<Integer> seen = new HashSet<>();  //store all numbers that is already part of result numbers
//        int count = 0;
//        for(int num : nums){
//            if(!set.contains(target - num)) {
//                set.add(num);
//            } else if (set.contains(target-num) && !seen.contains(num)){
//                count++;
//                seen.add(target-num);
//                seen.add(num);
//            }
//        }
//
//        return count;
//
//    }


    //two pointers
    //time complexity O(nlogn)
    //space complexity O(1)
//    public static int twoSumPairs(int[] nums, int target) {
//        Arrays.sort(nums);
//        int start = 0;
//        int end = nums.length - 1;
//        int count = 0;
//        while(start < end){
//            int sum = nums[start] + nums[end];
//            if(sum > target) end--;
//            else if(sum < target) start++;
//            else if(sum == target){
//                if((start == 0 || nums[start] != nums[start-1]) && (end == nums.length - 1 || nums[end] != nums[end = 1])){
//                    count++;
//                }
//                start++;
//                end--;
//            }
//        }
//
//        return count;
//
//    }
}