I have two different solutions for classic two sum problem, one is using the hashmap to traverse the list once, and another one is using two indexes and a sorted array to find the solution. The time complexity of using hashmap is O(n), and O(nlog(n)) on the other method, however, the running time report shows using the sorted array is faster than using map. Why?
Method 1: Using hashmap
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(target - numbers[i])) {
result[1] = i + 1;
result[0] = map.get(target - numbers[i]);
return result;
}
map.put(numbers[i], i + 1);
}
return result;
}
Method 2: using two indexes and a sorted array
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] sorted_nums = new int[nums.length];
for(int i = 0; i < nums.length; i++) {
sorted_nums[i] = nums[i];
}
Arrays.sort(sorted_nums);
int begin = 0;
int end = sorted_nums.length - 1;
while(begin < end) {
if(sorted_nums[begin] + sorted_nums[end] == target)
break;
else if(sorted_nums[begin] + sorted_nums[end] > target)
end--;
else
begin++;
}
int[] result = new int[2];
int idx = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] == sorted_nums[begin] || nums[i] == sorted_nums[end])
result[idx++] = i;
}
return result;
}
}
