This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given an array of integers, return **indices** of the two numbers such that they add up to a specific target.

You may assume that each input would have ** exactly** one solution, and you may not use the

**Example:**

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0,1].

b'

\n## Solution

\n

\n#### Approach #1 (Brute Force) [Accepted]

\n\n

\n#### Approach #2 (Two-pass Hash Table) [Accepted]

\n\n

\n#### Approach #3 (One-pass Hash Table) [Accepted]

\n\n

'
\n\n

\n\n

The brute force approach is simple. Loop through each element and find if there is another value that equals to .

\npublic int[] twoSum(int[] nums, int target) {\n for (int i = 0; i < nums.length; i++) {\n for (int j = i + 1; j < nums.length; j++) {\n if (nums[j] == target - nums[i]) {\n return new int[] { i, j };\n }\n }\n }\n throw new IllegalArgumentException("No two sum solution");\n}\n

**Complexity Analysis**

- \n
- \n
Time complexity : .\nFor each element, we try to find its complement by looping through the rest of array which takes time. Therefore, the time complexity is .

\n \n - \n
Space complexity : .

\n \n

\n

To improve our run time complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.

\nWe reduce the look up time from to by trading space for speed. A hash table is built exactly for this purpose, it supports fast look up in *near* constant time. I say "near" because if a collision occurred, a look up could degenerate to time. But look up in hash table should be amortized time as long as the hash function was chosen carefully.

A simple implementation uses two iterations. In the first iteration, we add each element\'s value and its index to the table. Then, in the second iteration we check if each element\'s complement () exists in the table. Beware that the complement must not be itself!

\npublic int[] twoSum(int[] nums, int target) {\n Map<Integer, Integer> map = new HashMap<>();\n for (int i = 0; i < nums.length; i++) {\n map.put(nums[i], i);\n }\n for (int i = 0; i < nums.length; i++) {\n int complement = target - nums[i];\n if (map.containsKey(complement) && map.get(complement) != i) {\n return new int[] { i, map.get(complement) };\n }\n }\n throw new IllegalArgumentException("No two sum solution");\n}\n

**Complexity Analysis:**

- \n
- \n
Time complexity : .\nWe traverse the list containing elements exactly twice. Since the hash table reduces the look up time to , the time complexity is .

\n \n - \n
Space complexity : .\nThe extra space required depends on the number of items stored in the hash table, which stores exactly elements.

\n \n

\n

It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element\'s complement already exists in the table. If it exists, we have found a solution and return immediately.

\npublic int[] twoSum(int[] nums, int target) {\n Map<Integer, Integer> map = new HashMap<>();\n for (int i = 0; i < nums.length; i++) {\n int complement = target - nums[i];\n if (map.containsKey(complement)) {\n return new int[] { map.get(complement), i };\n }\n map.put(nums[i], i);\n }\n throw new IllegalArgumentException("No two sum solution");\n}\n

**Complexity Analysis:**

- \n
- \n
Time complexity : .\nWe traverse the list containing elements only once. Each look up in the table costs only time.

\n \n - \n
Space complexity : .\nThe extra space required depends on the number of items stored in the hash table, which stores at most elements.

\n \n