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];
? ? }
}
總結(jié)：
還有一種方法，? 先排序，再使用雙指針首位相向而行。 但是，排序后每一個element的位置會打亂，對于此題要求的輸出不適用。
