publicint[] twoSum(int[] nums, int target) { // Assume nums is not null int n = nums.length; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { // j = i + 1 since we cannot use the same element twice if (nums[i] + nums[j] == target) { returnnewint[] { i, j }; } } } thrownew IllegalArgumentException("No two-sum solution"); }

1

Time: $O(N^2)$ 18 ms Space: $O(1)$

Hash Table

Note: The order of the indices in the return array does not matter.

Reduce the look-up time from $O(N)$ to $O(1)$ by trading space for speed.

Two-pass:2 ms

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

publicint[] twoSum(int[] nums, int target) { // Assume nums is not null int n = nums.length; Map<Integer, Integer> map = new HashMap<>(); // <val, idx> for (int i = 0; i < n; ++i) { map.put(nums[i], i); } for (int i = 0; i < n; ++i) { int val = target - nums[i]; if (map.containsKey(val) && map.get(val) != i) { returnnewint[] { map.get(val), i }; } } thrownew IllegalArgumentException("No two sum solution"); }

One-pass:2 ms

1 2 3 4 5 6 7 8 9 10 11 12 13

publicint[] twoSum(int[] nums, int target) { // Assume nums is not null int n = nums.length; Map<Integer, Integer> map = new HashMap<>(); // <val, idx> for (int i = 0; i < n; ++i) { int val = target - nums[i]; if (map.containsKey(val)) { returnnewint[] { map.get(val), i }; } map.put(nums[i], i); } thrownew IllegalArgumentException("No two sum solution"); }