Count pairs with given sum

Question

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

• Qwertie: What are pairs in this situation? Do they have to be next to each other? Do 3 in a row count as 1 pair, 2 pairs or none?

Answer 1

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 < 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 < len(nums) and nums[start] == nums[start+1]:
 start_count += 1
 start += 1
 while end-1 >= 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 < target_sum:
 start += 1
 else:
 end -= 1
 return total

• Graipher: You could use collections.Counter for the count dictionary .

Answer 2

• A stylistic comment first. It will not give you a performance boost, but nevertheless: for i in range() is very non-Pythonic. Consider

  for x in numbers:
   for y in numbers:
   if x + y == target:
   ....
  

• As for performance, sort your numbers first, and for each number x search for a range taken by target - x. It can be done in a logarithmic time.

• Peilonrayz: Hmm, for i in range() is very Pythonic, for i in range(len(A)): A[i] however isn't... Also your first gives incorrect output, I'm sure you know, but it's worth mentioning.
• Graipher: Also, sorting is n*log(n), not log(n), unless I'm mistaken.