The 2-SUM Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 5: | Line 5: | ||
=Overview= | =Overview= | ||
Given as input an input of n numbers, in no particular order, and a target sum t, find all pairs of integers that sum to t. | |||
The naive solution would be to double loop over the array in O(n<sup>2</sup>) running time. | |||
The better solution (that comes with an extra space requirement, though) is to insert all numbers in a [[Hash_Table#Canonical_Use|hash table]] and then do a second pass where for each number we look to see if (t - x<sub>i</sub>) exists in the table. This is a O(n) solution. | |||
Revision as of 20:29, 16 October 2021
Internal
Overview
Given as input an input of n numbers, in no particular order, and a target sum t, find all pairs of integers that sum to t.
The naive solution would be to double loop over the array in O(n2) running time.
The better solution (that comes with an extra space requirement, though) is to insert all numbers in a hash table and then do a second pass where for each number we look to see if (t - xi) exists in the table. This is a O(n) solution.