O(n^2) I got Time Limit Exceed. Does anyone got accept by O(n^2) ? I just use binary search and finally accept.
This problem O(n^2) is ok?

You may use HashTable and solve the problem in O(N) time / O(N) space complexity
import java.util.Hashtable; //import hashtable utility public class Solution { public int[] twoSum(int[] numbers, int target) { int []a = new int[2]; Hashtable<Integer, Integer> nums = new Hashtable<Integer, Integer>(); for (int i=0; i<numbers.length; i++) { //put number into hash table (if it's not already there) Integer n = nums.get(numbers[i]); if (n==null) nums.put(numbers[i], i); //subtract array element from target number n = nums.get(targetnumbers[i]); if (n!=null && n<i) {//if such number exists in the table return the indicies a[0]=n+1; a[1]=i+1; return a; } } return a; } }

This following
O(n^2)
solution was accpeted by the judge.class Solution { public: vector<int> twoSum(vector<int> &numbers, int target) { int i,j; vector<int> v; for(i=0;i<numbers.size();i++) for(j=i+1;j<numbers.size();j++) if(numbers[i]+numbers[j]==target) { v.push_back(i+1); v.push_back(j+1); return v; } } };
EDIT : The first time, I submitted this code it got accepted in 40ms but the same code now gives a TLE.

Given the assumption "each input would have exactly one solution" the above implementation should work with duplicates as well. In the example above, when first 3 is encountered, the loop would check if targetnumbers[i] (63=3) exists in hash table. It does not, thus 3 is put into the hash table. When second 3 is encountered the loop again checks (63). This time 3 exists in the hash, thus returns indices of 3 and 3 from numbers array.

I was trying using the hash solution, and i found I got the result of the identical positions , say [2, 2], cuz as checking 'target  numbers[i]' it would get the 3 from where i just put in hash, 'nums.put(numbers[i], i)'. And I found mine didn't have the condition 'n < i'.
Finally, my solution is check target  numbers[i] first, if found, then just return. Otherwise put the current value into hash table.

import java.util.Hashtable; //import hashtable utility public class Solution { public int[] twoSum(int[] numbers, int target) { // Start typing your Java solution below // DO NOT write main() function HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); int n = numbers.length; int[] result = new int[2]; for (int i = 0; i < numbers.length; i++) { if (map.containsKey(target  numbers[i])) { result[0] = map.get(targetnumbers[i]) + 1; result[1] = i + 1; break; } else { map.put(numbers[i], i); } } return result; } }