O(nlogn) Binary Search | Beats 100% Python
Explanation\nThe main idea behind the solution is that \nif a + b < target, then b < target - a\n\nThus, for every element a in nums, finding all possible pairs
# Explanation\nThe main idea behind the solution is that \nif $$a + b < target$$, then $$b < target - a$$\n\nThus, for every element `a` in `nums`, finding all possible pairs containing `a` that have a sum less than `target` is the same as finding number of elements in `nums` that are less than `target - a`.\n\nOne more step that we need to do to avoid duplicates is that to find pairs of an element at index `i`, we binary search `nums` starting from index `i + 1`\n\n# Complexity\nLet $$n$$ be the length of `nums`\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$ for sorting\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def countPairs(self, nums: List[int], target: int) -> int:\n        nums = sorted(nums)\n        pairs = 0\n        for i, n in enumerate(nums):\n            value = target - n\n            pairs += self.binarySearchLessThan(i + 1, value, nums)\n        return pairs\n\n    def binarySearchLessThan(self, start: int, value: int, nums: List[int]) -> int:\n        \'\'\'Return the number of elements in nums[start:] that are lesser than value.\n        nums[start:] must be sorted in non-decreasing order.\n        \'\'\'\n        left, right = start, len(nums)\n\n        while left < right:\n            middle = (left + right) // 2\n            if nums[middle] < value:\n                left = middle + 1\n            else:\n                right = middle\n\n        return left - start\n\n                    \n        \n```
['Python3']