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



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

    }

      //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 counted in previous if, but this should be count, and only this should be counted
//                    count++;
//                }
//            }
//        }
//        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;
//
//    }
}

    If numbers in list is unique: for example [1,2,3,4] target=5. This can be easily solved by using one HashSet. We can just iterate the array and store every number in set, whenever we meet the target-num, count plus plus.
If numbers is not unique: for example [1,4,4] target = 5. In this case, we can only have first 4 to pair with 1 to sum up to 5; the second 4 can not be stored. But there is a special case, if array is still [1,4,4], but target = 8, we should pair the first 4 and second 4 to sum up to 8.
This may still be able to solve with one set, but I imagine that there would be a lot of if else clause in this solution. 
Then I wonder maybe I can have another HashSet. In this set, I am going to store all numbers that is already part of result pairs. Then if I see these number again, I will not consider them as result since they are already part of the result numbers. 
Here comes my solution, the first HashSet set is used to store all unique numbers during iteration, the second HashSet seen is used to store all numbers that is already part of result numbers….

use one set, then need to sort, time complexity O(nlogn), space complexity O(n).
use two pointers, also need to sort, time complexity O(nlogn), space complexity O(1).