Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

twoSum Algorithm : How to improve this?

Tags:

java

I felt like doing an algorithm and found this problem on leetcode

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

My solution is O(n^2). I wanted to know if there is better way of doing this? like O(n) or O(nlogn)

import java.util.Arrays;
public class ReturnIndex {
    public int[] twoSum(int[] numbers, int target) {
        int tail = numbers.length-1;
        int[] n = new int[2];
        for (int i=0;i<tail;i++) {
            for(int j=i+1;j<tail;j++) {
                if(target ==(numbers[i]+numbers[j])) {
                    n[0] = i+1;
                    n[1] = j+1;
                }
            }
        }
        return n;
    }

    public static void main(String[] args) {
        int[] s = {150,24,79,50,88,345,3};
        int value = 200;
        ReturnIndex r = new ReturnIndex();
        int[] a = r.twoSum(s,value);
        System.out.println(Arrays.toString(a));
    }
}
like image 634
SuperMan Avatar asked Oct 24 '12 03:10

SuperMan


1 Answers

Here is an O(n):

public int[] findSumMatched(int[] numbers, int target) {
    Map<Integer, Integer> mapOfNumbers = new HashMap<Integer, Integer>();
    for (int i = 0; i<numbers.length; i++) {
        int secondNumber = target - numbers[i];
        if (mapOfNumbers.get(secondNumber) != null){
            return new int[] {mapOfNumbers.get(secondNumber), i};
        }
        mapOfNumbers.put(numbers[i], i);
    }
    throw new IllegalArgumentException();
}
like image 185
miserable Avatar answered Oct 12 '22 20:10

miserable