Last Updated: February 25, 2016
·
1.038K
· pritz2

Find 2 Integers in an array that add up to SUM

A common interview question for undergraduates looking for an internship is "Given an unsorted array of positive integers, find 2 numbers that add up to SUM."

I see many solutions wherever I look on the web. The simplest and most obvious is O(n^2). Some include sorting first (which is O(nlogn) at least). Others produce counting arrays, index arrays, etc.

By far the most clever is to use a hash table. To produce a perfect hash table would cost a large amount of time, it is at least a constant amount of time. But hash tables, at their essence, are just arrays. Instead of using a built-in Hash Table data structure, you can make an array yourself, and check the array as you go through it.

Quick code writeup below:

typedef int bool;
enum { false, true };

#define ARRAY_LENGTH 7
int array[ARRAY_LENGTH] = {5, 12, 18, 4, 3, 27, 2};

bool function(int SUM) {
    int index[SUM];
    for(int i = 0; i < ARRAY_LENGTH; i++) {
        if( array[i] < SUM ) {
            if( index[SUM-array[i]] == true ) {
                printf("%d and %d add up to %d",array[i], SUM-array[i], SUM);
                return true;
            }
            index[array[i]] = true;
        }
    }
    return false;
}

Not only is this an O(n) function, but it stops immediately upon finding the first pair of numbers, instead of continuing through the entire array.