Python O(n log n) solution using quicksort and two pointers
Approach\n1. Sort the array in ascending order\n2. Start left pointer and right pointer\n3. Iterate while left pointer is different than right pointer\n4. Verif
# Approach\n1. Sort the array in ascending order\n2. Start left pointer and right pointer\n3. Iterate while left pointer is different than right pointer\n4. Verify if the sum of `nums[left]` and `nums[right]` is less than target, if it is, then you have new `(right - left)` combinations, after adding the new combinations increment the left pointer\n5. If the sum of those two numbers is not less than target, than decrement the right pointer\n\n# Complexity\n- Time complexity: O (n log n)\n\n# Code\n```\nimport math\n\nclass Solution:\n    def countPairs(self, nums: List[int], target: int) -> int:\n        sortedNums = self.quicksort(nums) # time complexity: O (n log n)\n        left = 0\n        right = len(nums) - 1\n        pairs = 0\n        \n        while left != right:\n            sumNumbers = sortedNums[left] + sortedNums[right]\n            \n            if sumNumbers < target:\n                pairs += right - left\n                left += 1\n            else:\n                right -= 1\n        \n        return pairs\n        \n    def quicksort(self, numbers):\n        if (len(numbers) < 2):\n            return numbers\n        else:\n            pivotIndex = math.floor(len(numbers) / 2)\n            pivot = numbers[pivotIndex]\n\n            lowerThanPivot = []\n            greaterThanPivot = []\n\n            for i, n in enumerate(numbers):\n                if (i == pivotIndex): continue\n\n                if (n <= pivot): lowerThanPivot.append(n)\n                else: greaterThanPivot.append(n)\n\n            return self.quicksort(lowerThanPivot) + [pivot] + self.quicksort(greaterThanPivot)\n```
['Python3']