publicint[] twoSum(int[] nums, int target) { // Assume nums is not null intn= nums.length; for (inti=0; i < n; ++i) { for (intj= 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 }; } } } thrownewIllegalArgumentException("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 intn= nums.length; Map<Integer, Integer> map = newHashMap<>(); // <val, idx> for (inti=0; i < n; ++i) { map.put(nums[i], i); } for (inti=0; i < n; ++i) { intval= target - nums[i]; if (map.containsKey(val) && map.get(val) != i) { returnnewint[] { map.get(val), i }; } } thrownewIllegalArgumentException("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 intn= nums.length; Map<Integer, Integer> map = newHashMap<>(); // <val, idx> for (inti=0; i < n; ++i) { intval= target - nums[i]; if (map.containsKey(val)) { returnnewint[] { map.get(val), i }; } map.put(nums[i], i); } thrownewIllegalArgumentException("No two sum solution"); }