2

I thought a way to solve the problem which has the following code:

package samueg.algorithm;

public class Main {

    public static void main(String[] args) {
        int[] numbers = new int[] { -1, 3, 7, 2, 4, 5, -8, 9 };
        int sum = 14;
        int targetIndex1 = -1, targetIndex2 = -1;
        for (int i = 0; i < numbers.length; ++i) {

//          for (int j = 0; j < i; ++j) {
//              if (numbers[i] + numbers[j] == sum) {
//                  targetIndex1 = i;
//                  targetIndex2 = j;
//                  break;
//              }
//          }

            for (int j = (i + 1); j < numbers.length; ++j) {
                if (numbers[i] + numbers[j] == sum) {
                    targetIndex1 = i;
                    targetIndex2 = j;
                    break;
                }
            }

            if (targetIndex1 != -1 && targetIndex2 != -1) {
                System.out.println(String.format("%1$d + %2$d = %3$d",
                        numbers[targetIndex1], numbers[targetIndex2], sum));
                return;
            }
        }

        System.out.println("No targets which satisfy the condition are found.");

    }

}

The commented code is not necessary because the judgements they do are already done for index i. I want to know whether this algorithm is efficient or not and if it's not can someone show me a better one? Thanks.

Samuel Gong
  • 157
  • 1
  • 1
  • 7
  • 2
    The complexity is O (n^2). Can be done ib O (nlogn) by first sorting the array and then iterating in forward and backward direction simultaneously. – Abhishek Bansal Jan 07 '14 at 17:52

2 Answers2

3

Using a hash table:

For each number n:

  • Check if target number - n is in the hash table. If it is, we've found two numbers summing to the target number.

  • Insert n into the hash table.

Complexity: Expected O(n) (your approach is O(n2) because of the double for loop).

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
  • 1
    This is certainly a good choice if you have a large set of numbers. Caution is warranted if you are doing lots of small arrays (constant factors are probably higher for setting up and managing the amortized hash table internals) – Speed8ump Jan 07 '14 at 20:56
1

Sort the array, set two pointers and move them separately. This should give you a O(n log(n)) solution. I'm not good in java so let me python:

def find_indexes(A, s):
    A = sorted(A)
    p1 = 0
    p2 = len(A) - 1
    while not A[p1] + A[p2] == s and p1 < len(A) and p2 >= 0:
        if A[p1] + A[p2] < s:
            p1 = p1 + 1
        if A[p1] + A[p2] > s:
            p2 = p2 - 1
    if A[p1] + A[p2] == s:
        return (p1,p2)
    return None
Łukasz Kidziński
  • 1,613
  • 11
  • 20