2 sum
Solution 1:
iteration using 2 for loop
Time : O(N^2), Space: O(1)
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int [] {i, j};
}
}
}
return new int[2];
}
}
Solution 2:
store (value, index) pair in HashMap,
iterate the number array, O(1) time to find the index for the complement target value
Time: O(N) , Space: O(N)
class Solution { public int[] twoSum(int[] nums, int target) { Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i]) && map.get(target - nums[i]) != i) {
return new int[] {i, map.get(target - nums[i])};
}
}
return new int[2];
}
}
improvement:
class Solution { public int[] twoSum(int[] nums, int target) { Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[] {i, map.get(target - nums[i])};
} else {
map.put(nums[i], i);
}
}
return new int[2];
}
}
总结：
还有一种方法， 先排序，再使用双指针首位相向而行。 但是，排序后每一个element的位置会打乱，对于此题要求的输出不适用。
