Given a set of numbers -50 to 50, find all pairs that add

O(n^2) solution is just two double for loops.

O(n log n) solution will use a binary tree

O(n) solution will use a hash table

O(n) solution possibility (no need for a data structure)
void findpairs(int sum)
{
//given a set of numbers -50 to 50, find all pairs that add up to a certain sum that is passed in.

    if (sum == 0)
    {
        cout 0)
    {
        for(int i = 0; i((sum/2)-1) && i>-26; i--)
        {
            if( (i - sum+i) == sum)
            {
                cout << i << " " << sum+i << "\n";
            }
        }
    }
}

@Mike
"if( (i + sum-i) == sum)"

will always give you "sum".

@Mike:
if (sum == 0) does not imply 0,0.
It implies -50,50; -49,49; -48,48,...

Has anyone found the O(n) solution??? I'm having trouble with this one...

Put all the numbers from the array into a hash. So, keys will be the number and values of the keys be (sum-key). This will take one pass. O(n).

Now, foreach key 'k', with value 'v':
  if k == v:
     there is a match and that is your pair.
this will take another O(n) pass

totale O(2n) ~ O(n)

Easiest way to do it. Written in python. If you consider the easiest case, when our summed value (k) is 0, the pairs will look like

-50 + 50
-49 + 49
-48 + 48
etc....
etc... So what I do is generalize the situation to be able to shift this k value around. I also allow us to change our minimums and maximums. This solution assumes pairs are commutative, i.e. (2, 3) is the same as (3, 2).

Once you have the boundaries that you need to work with, you just march in towards k / 2. This solution runs in O(n) time.

def pairs(k, minimum, maximum):
    if k >= 0:
        x = maximum
        y = k - maximum
    else:
        x = k + maximum
        y = minimum
    while x >= k / 2 and y <= k / 2:
        print str(x) + " , " + str(y) + " = " + str(x + y)
        x = x - 1
        y = y + 1

here is my solution using hash table that runs in O(2n) => O(n):

 public static String findNums(int[] array, int sum){
        String nums = "test";

        Hashtable lookup = new Hashtable();

        for(int i = 0; i < array.length; i++){
            try{
            lookup.put(array[i], i);
            } catch (NullPointerException e) {
                System.out.println("Unable to input data in Hashtable: " + e.getMessage());
            }
        }

        int num2;
        int num1;

        for (int i = 0; i < array.length; i++){
            num2 = sum - array[i];
            Integer index = (Integer)lookup.get(num2);
            if ((lookup.containsKey(num2)) && (index != i)){
                num1 = array[i];
                nums = array[i] + ", and " + num2;
                return nums;
            }
        }

        //System.out.println(lookup.get(-51));

        return "No numbers exist";
     }

The number you're looking for is T.

You can just create an array of size 101.
Then you loop through the array, and drop each number i in cell of index i-50.
Now you do a second pass, and for each number, you look at the number at index T-i-50. If there's something there, you have a pair.

typedef pair Pair;
list l; //create an empty list of tuples
pairofsum(l,10); // an example of how to call the function which adds to your list of tuples the possible pairs of the sum

void pairofsum(list& l,int sum)
{
    if(sum==0)
    {
        Pair p;
        loadPair(p,0,0);
        l.push_back(p);
        for(int i=1;i<51;i++)
        {
            loadPair(p,i, -i);
            l.push_back(p);
        }
    }
    else if (sum<0)
    {
        Pair p;
        for(int i=0;i+-sum<51;i++)
        {
            loadPair(p,i,-(i+-sum));
            l.push_back(p);
        }
        for(int i=1;i<=-sum/2;i++)
        {
                loadPair(p,-i,sum+i);
                l.push_back(p);
        }
    }
    else
    {
        Pair p;
        for(int i=1;sum+i<51;i++)
        {
            loadPair(p,-i,sum+i);
            l.push_back(p);
        }
        for(int i=0;i<=sum/2;i++)
        {
            loadPair(p,i,sum-i);
            l.push_back(p);
        }
    }
}

void loadPair(Pair& p, int f, int s)
{
    p.first=f;
    p.second=s;
}

Here is my C# implementation. It runs O(N) and doesn't include duplicate pairs (e.g. including [50,-50] as well as [-50,50]).

static void FindPairs(int sum) {
    for (int i=-50; i=-50) {
            Console.WriteLine(i + " " + otherNum);
        }
    }
}

Solution with no duplicates:

    @Test
    public void findPairsTest() {
        // TestCases
        // Alternately you can put this test cases in dataprovdier
        findPairs(50);
        findPairs(20);
        findPairs(-20);
        findPairs(-50);
        findPairs(0);
    }

    private void findPairs(Integer sum) {
        HashMap inputPair = new HashMap();
        HashMap outputPair = new HashMap();

        for(int i=-50; i<=50; i++) {
            inputPair.put(i, sum-i);
        }

        // print pairs
        for(Integer key : inputPair.keySet()) {
            Integer potentialOtherNum = inputPair.get(key);
            if(inputPair.containsKey(potentialOtherNum) && potentialOtherNum < key) {
                outputPair.put(key, potentialOtherNum);

            }
        }

        System.out.println(outputPair.entrySet().toString());
    }

Here is the solution in O(n) time complexity.
http://www.knowsh.com/Notes/NotesSearch/NotesDetail/140226/Program-To-Find-All-The-Pairs-In-The-Given-Set-That-Add-Up-To-A-Certain-Sum

Please let me know if there is any thing I missed.

Use two pointers, one at the begin, one at the end, let us call the pointer begin and end, the array is named nums. If nums[begin]+nums[end]>target, end--;if end

Half=sum/2;
i=1;
While (half+i -51) {
             first = half-i;
             second = half+i;
             System.out.println(“” + first + “, “ + second);
}

half=sum/2;
i=1;
While (half+i \ -51) {
             first = half-i;
             second = half+i;
             System.out.println(“” + first + “, “ + second);
}