O(n^2) is too slow

• O(n^2) solution is the simplest solution for this but complains about the running time. I used HashMap so that it maintains O(n) for average cases.

1. Basically put all numbers in a HashMap (key: numbers, values: indices)
2. Loop through every HashMap element and check if target minus key value exists

Here is my accepted code:

public class Solution {
public int[] twoSum(int[] numbers, int target) {
int length = numbers.length;
int [] output = {-1, -1};
HashMap <Integer, ArrayList<Integer>> hm = new HashMap <Integer, ArrayList<Integer>>();
for (int i = 0; i < length; i++) {
if (!hm.containsKey(numbers[i])) {
ArrayList<Integer> al = new ArrayList<Integer>();
hm.put(numbers[i], al);
}
else {
int key = numbers[i];
}
}
for (int key : hm.keySet()) {
ArrayList<Integer> al = hm.get(key);
int num1 = al.get(0);

if (hm.containsKey(target - key)) {
if (hm.get(target-key).size() > 0) {
al.remove(0);
output[0] = num1;
output[1] = hm.get(target-key).get(0);
Arrays.sort(output);
return output;
}
}
}
return output;
}
}

• if numbers is {3, 2, 5, 9, 9, 7}, you will error。You need to make a little change.like that：

public int[] twoSum2(int[] numbers, int target) {
int length = numbers.length;
int[] output = { -1, -1 };
HashMap<Integer, ArrayList<Integer>> hm = new HashMap<Integer,ArrayList<Integer>>();
for (int i = 0; i < length; i++) {
if (!hm.containsKey(numbers[i])) {
ArrayList<Integer> al = new ArrayList<Integer>();
hm.put(numbers[i], al);
} else {
int key = numbers[i];
}
}
for (int key : hm.keySet()) {
ArrayList<Integer> al = hm.get(key);
int num1 = al.get(0);

if (hm.containsKey(target - key)) {
if (target - key == key && al.size() > 1) {
al.remove(0);
output[0] = num1;
output[1] = hm.get(target - key).get(0);
Arrays.sort(output);
return output;
} else if (target - key != key) {
output[0] = num1;
output[1] = hm.get(target - key).get(0);
Arrays.sort(output);
return output;
}
}
}
return output;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.