Count pairs with given sum I want to find the number of the pairs in an array that equal a given sum.

I've naively tried to implement brute force as a solution, but it is too slow and this task should not take more than one second. 

def getPairsCount(numbers, shouldEqualTo):
    count = 0
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] + numbers[j] == shouldEqualTo:
                count += 1
    return count
If you can use extra space :

# O(n) running time / O(n) memory
def get_pair_count(nums, target_sum):
    count = {}
    for num in nums:
        count[num] = count.get(num, 0) + 1

    total_double = 0
    for num in nums:
        complement = target_sum - num
        if complement in count:
            total_double += count[complement]
            if complement == num:
                total_double -= 1
    return total_double // 2


source : http://www.geeksforgeeks.org/count-pairs-with-given-sum/

If you can't use more space you could try this version I just made (at your own risk)

 # O(n log n) running time / O(1) memory
def get_pair_count_no_extra_memory(nums, target_sum):
    nums.sort()
    start = 0
    end = len(nums) - 1
    total = 0

    while start &lt; end:
        current_sum = nums[start] + nums[end]
        if current_sum == target_sum:
            start_count = 1
            end_count = 1
            special_case = False
            if nums[start] == nums[end]:
                special_case = True

            while start+1 &lt; len(nums) and nums[start] == nums[start+1]:
                start_count += 1
                start += 1
            while end-1 &gt;= 0 and nums[end] == nums[end-1]:
                end_count += 1
                end -= 1

            if special_case:
                total += ((start_count - 1) * start_count) // 2
            else:
                total += start_count * end_count
            start += 1
            end -= 1
        elif current_sum &lt; target_sum:
            start += 1
        else:
            end -= 1

    return total