How can I find two elements in an array that sum to k

Question

Suppose you are given an array of unsorted integers as

A = {3,4,5,1,4,2}

Input : 6 Output : {5,1}, {4,2}

How can I do this in O(n) or O(log n). Any suggestions will be appreciated.

Update: Can we write something more efficient than this?

for(int i=0;i<array.length-1;i++)  
{  
    if(array[i]+array[i+1]==6)  
        System.out.println("{"+array[i]+","+array[i+1]+"}");  
}  

Answer 1

If the numbers stored in the input array are only positive then I'd create another array K of k+1 ArrayList elements. Where k is the number you need them to add up to. Only two numbers less than k can add up to k (assuming we deal with positive ints} or in special case {0,k}. Then I would iterate through all elements of input array and for each int m that is less or equal to k I'd take its index and add that index to the array of ArrayList K at index m. Then I would iterate through first half of the array K and for each index i that has some ints stored in it I would find complementary index [k-i] and see if there are any values in it. If there are then those are your pairs. And btw this is O(n).

public static void findElemtsThatSumTo( int data[], int k){
    List arrayK[]= new List[k+1];
    for(int i=0; i<arrayK.length; i++)
        arrayK[i]= new ArrayList<Integer>();

    for(int i=0; i<data.length; i++){
        if(data[i]<=k)
            arrayK[data[i]].add(i);
    }

    for(int i=0; i<arrayK.length/2; i++){
        if(!arrayK[i].isEmpty() && !arrayK[k-i].isEmpty())
        {
            for(Object index: arrayK[i])
                for(Object otherIndex: arrayK[k-i])
                    System.out.println("Numbers at indeces ["+index.toString()+", "+otherIndex.toString()+"] add up to "+k+".");
        }
    }

}

Answer 2

public static void main(String[] args) {
    // TODO Auto-generated method stub

    int arr[]={4,2,6,8,9,3,1};
    int sum=10;
    int arr1[]=new int[sum];


    for(int x=0;x<arr.length;x++)
    {
        arr1[arr[x]]++;
    }

    for(int y=0;y<arr.length;y++)
    {
        if(arr1[sum-arr[y]]==1)
        {
            System.out.println(arr[y]+","+(sum-arr[y]));
        }
    }

}

Answer 3

My little answer about this problem for O(n) complexity with O(n) additional memory. This code snippet returns all unique indices pair of elements with sum K.

/**
 * Returns indices of all complementary pairs in given {@code arr} with factor {@code k}. Two elements {@code arr[i]} and {@code arr[j]} are
 * complementary if {@code arr[i] + arr[j] = k}.
 * Method returns set of pairs in format {@literal [i,j]}. Two pairs {@literal [i,j]} and {@literal [j,i]} are treated as same, and only one pair
 * is returned.
 * Method support negative numbers in the {@code arr}, as wel as negative {@code k}.
 * <p>
 * Complexity of this method is <t>O(n)</t>, requires <t>O(n)</t> additional memory.
 *
 * @param arr source array
 * @param k   factor number
 * @return not {@code null} set of all complementary pairs in format {@literal [i,j]}
 */
public static Set<String> getComplementaryPairs(int[] arr, int k) {
    if (arr == null || arr.length == 0)
        return Collections.emptySet();

    Map<Integer, Set<Integer>> indices = new TreeMap<>();

    for (int i = 0; i < arr.length; i++) {
        if (!indices.containsKey(arr[i]))
            indices.put(arr[i], new TreeSet<>());
        indices.get(arr[i]).add(i);
    }

    Set<String> res = new LinkedHashSet<>();

    for (Map.Entry<Integer, Set<Integer>> entry : indices.entrySet()) {
        int x = entry.getKey();
        int y = k - x;

        if (x == y) {
            int size = entry.getValue().size();

            if (size < 2)
                continue;

            Integer[] ind = entry.getValue().toArray(new Integer[size]);

            for (int j = 0; j < size - 1; j++)
                for (int m = j + 1; m < size; m++)
                    res.add(String.format("[%d,%d]", ind[j], ind[m]));
        } else if (x < y && indices.containsKey(y))
            for (int j : entry.getValue())
                for (int m : indices.get(y))
                    res.add(String.format("[%d,%d]", j, m));
    }

    return res;
}

Answer 4

As with your other question, O(log n) is impossible, since you have to examine the entire array. But O(n) is more or less possible.

If your range of possible integers is relatively small — that is, if it's within a constant factor of n — then you can write:

final boolean[] seen = new boolean[max - min + 1];
for(final int a : A)
{
    if(seen[input - a - min])
        System.out.println("{" + (input - a) + "," + a + "}");
    seen[a - min] = true;
}

If not, you can do the same thing, but using a HashSet<Integer> instead of an array:

final Set<Integer> seen = new HashSet<Integer>();
for(final int a : A)
{
    if(seen.contains(input - a))
        System.out.println("{" + (input - a) + "," + a + "}");
    seen.add(a);
}

but that will not have guaranteed O(n) time.