Python Elegant & Short | Brute-Force vs Greedy | O(n*log(n))
Complexity\n- Time complexity: O(n^{2})\n- Space complexity: O(1)\n\n# Brute-Force\n\nclass Solution:\n    def countPairs(self, nums: List[int], target: int) ->
# Complexity\n- Time complexity: $$O(n^{2})$$\n- Space complexity: $$O(1)$$\n\n# Brute-Force\n```\nclass Solution:\n    def countPairs(self, nums: List[int], target: int) -> int:\n        return sum(\n            a + b < target\n            for a, b in combinations(nums, 2)\n        )\n```\n\n# Complexity\n- Time complexity: $$O(n * \\log_2{n})$$\n- Space complexity: $$O(1)$$\n\n# Greedy\n```\nclass Solution:\n    def countPairs(self, nums: List[int], target: int) -> int:\n        nums.sort()\n\n        lo, hi = 0, len(nums) - 1\n        pairs = 0\n\n        while lo < hi:\n            if nums[lo] + nums[hi] < target:\n                pairs += hi - lo\n                lo += 1\n            else:\n                hi -= 1\n\n        return pairs\n```
['Python3']