C++ O(nlogn) solution without hashmap [detail explanation]
Sort and then perform two scans in parallel, maintaining a difference as close to k as possible between the two scan positions. In other words, advance the lead
Sort and then perform two scans in parallel, maintaining a difference as close to k as possible between the two scan positions. In other words, advance the leading scan when the difference is smaller than k, and advance the lagging scan when the difference is greater. This way we either find a pair or scan through the list and report that no pair exists. Time complexity: O(n log n).\n\t\n\tclass Solution {\n\tpublic:\n\t\tint findPairs(vector<int>& nums, int k) {\n\t\t\tsort(nums.begin(),nums.end());\n\t\t\tint fast=1;\n\t\t\tint slow=0;\n\t\t\tint ans=0;\n\t\t\twhile(slow<nums.size() && fast<nums.size()){\n\t\t\t\tif(nums[fast]-nums[slow]==k){\n\t\t\t\t\tans++;\n\t\t\t\t\tfast++;\n\t\t\t\t\tslow++;\n\t\t\t\t\twhile(fast<nums.size() && nums[fast]==nums[fast-1]){\n\t\t\t\t\t\tfast++;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\telse if(nums[fast]-nums[slow]>k){\n\t\t\t\t\tslow++;  \n\t\t\t\t\tif(fast-slow==0){\n\t\t\t\t\t\tfast++;}\n\t\t\t\t}\n\t\t\t\telse{      \n\t\t\t\t\tfast++;\n\t\t\t\t}         \n\t\t\t}\n\t\t\treturn ans;\n\n\t\t}\n\t};
['C', 'Sorting', 'C++']