# Java, 2 solution, O(nlgn) time and O(1) space using sort and binarysearch, O(n) time and O(n) space using hash

• Solution 1, Sort and binary search, costs O(n) time and O(n) space using hash.

import java.util.Arrays;

``````public class SortSearchSolution {
public int[] twoSum(int[] numbers, int target) {
int start = 0, end = 0, temp;
int[] back = Arrays.copyOf(numbers, numbers.length);
int[] reslut = new int[] { 0, 0 };
Arrays.sort(back);
for (int i = 0; i < back.length; i++) {
start = Arrays.binarySearch(back, target - back[i]);
if (start > 0 && start != i) {
start = back[start];
end = back[i];
break;
}
}
for (int i = 0; i < numbers.length; i++)
if (numbers[i] == start) {
reslut[0] = i + 1;
break;
}
for(int i=0;i<numbers.length;i++)
if(numbers[i]==end&&i!=reslut[0]-1){
reslut[1]=i+1;
break;
}
if (reslut[0] > reslut[1]) {
temp = reslut[0];
reslut[0] = reslut[1];
reslut[1] = temp;
}
return reslut;
}
}
``````

Solution 2, HashMap, costs O(n) time and O(n) space.

``````import java.util.HashMap;
import java.util.Map;

public class Solution {
public int[] twoSum(int[] numbers, int target) {
Map<Integer, Integer> map=new HashMap<>(numbers.length*2);
for(int i=0;i<numbers.length;i++){
Integer company=map.get(target-numbers[i]);
if(company==null)
map.put(numbers[i], i);
else
return new int[]{company+1,i+1};
}
return null;
}
}
``````

But this two method do not have that much different in running as it should be. Method 1 costs me 220 ms, and method 2 costs me 241 ms.

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