An explanation Going from O(NlogN) -> O(N)
So, this problem is very similar to a very famous problem Two Sum problem. But a slightly different, there we have to only check wether a pair exists or not whi
So, this problem is very similar to a very famous problem `Two Sum` problem. But a slightly different, there we have to only check wether a pair exists or not which has 2 sum equals to the target. But here we have to count those such pairs & only consider the unique one.\n\n**Okay, so how we will solve this problem?**\n\n>One of the first idea came in mind that first-of all we sort this array. Let\'s take an example :-\n\n**Input:** nums = [3,1,4,1,5], k = 2\n**Output:** 2\n\nFirst we sort this array & it becomes :- [1,1,3,4,5]. After sorting what we will do is, start from the starting place & check the \'x + k\' exists on to right place or not!\n\n![image](https://assets.leetcode.com/users/images/525d936e-2f0e-435d-a65d-aa1fa0d50ee3_1644372336.409042.png)\n\nSo, first we sort the array & then we will look for the binary search. There is a `method in Java library` called **Arrays.binarySearch** & it may be available in `C++ & Python`. In this method we will pass the array [nums], start index [i + 1], end [n] "size of the array" & the value which we have to search [x + k]. If we find that we, then we will store minimum value of \'x\' into a set. Because we need only the **Unique Pair**.\n\nSo, we will get :- **{1,3} & {3,5}** so these are the 2 pairs we will get. \n\n***Let\'s look at the code you will understand more clearly then,***\n\n```\nclass Solution {\n    public int findPairs(int[] nums, int k) {\n        Arrays.sort(nums); // sorted the array\n        Set<Integer> set = new HashSet<>(); // Declare the HashSet to only consider unique one\'s\n        int n = nums.length; // length of the array\n        for(int i = 0; i < nums.length - 1; i++){\n            // searching for binary index for the no from the i + 1 index to n \n            // and check if we are getting nums[i] + k, where nums[i] is our \'x\'\n            if(Arrays.binarySearch(nums, i + 1, n, nums[i] + k) > 0){\n                set.add(nums[i]);\n            }\n        }\n        return set.size();\n    }\n}\n```\n**Time Complexity :-** O(NlogN) + O(N * logN) = O(NlogN) + O(NlogN) = O(2NlogN) = *BigO(NlogN)*\n\n<hr>\n<hr>\n\n> **Now, you we will ask**. Can we further improve it\'s time complexity? **I\'ll say yes. Using HashMap.**\n\nOkay, so considering the same example : nums[3,1,4,1,5]\n\nFirst we will build our HashMap. In Map we will keep the no. as a key & value as a count of occurence\n\n![image](https://assets.leetcode.com/users/images/16d72c73-6d89-4fcb-8bf0-db63867f5e1c_1644373538.138938.png)\n\nNow, there are 2 cases :-\n1. If k > 0, then in this case we just need to check wether the counter part exists or not. So, if we are iterating \'x + k\' in our map, then we can increment our count\n\n\n2. If k == 0, then we just need to check if x is more then 1 or not [x > 1] in our map.\n\nBut another thing we need to note that here as we iterate from the array after doing counting. Then we will get "1" two times. So, to avoid this instead of iterating over the array, we will iterate over the keyset of this map, which will give us the unique no. i.e. (3,1,4,5).\n\nAlright, so now *I hope approach is clear.*\n\n**Let\'s code it:**\n\n```\nclass Solution {\n    public int findPairs(int[] nums, int k) {\n        Map<Integer, Integer> map = new HashMap<>();\n        \n        for(int num : nums){\n            map.put(num, map.getOrDefault(num, 0) + 1);\n        }\n        int count = 0;\n        for(int x : map.keySet()){\n            if(k > 0 && map.containsKey(x + k) || k == 0 && map.get(x) > 1) count++;\n        }\n        return count;\n    }\n}\n```\nANALYSIS :-\n* **Time Complexity :-** BigO(N)\n\n* **Space Complexity :-** BigO(N)
[]