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));
}
}
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();
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With