Two Sum

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 same* element twice.

Example:

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

Java Approach

class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int;
for(int i = 0; i < nums.length; i++) {
for(int n = i + 1; n < nums.length; n++) {
if( nums[i] + nums[n] == target) {
res = i;
res = n;
}
}
}
return res;
}
}

Python Approach

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
res = []
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
res.append(i)
res.append(j)
return res

Idea：Use two level for loop to check every element。Idea is simple but time complexity = O(n^2)

Improvement

Trying to use hash map to store the index and value in nums. Because known there's the only solution in every list, if find a result in seen map, I just return both index of the result, and i.

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i, v in enumerate(nums):
remain = target - v
if remain in seen:
return [seen[remain], i]
seen[v] = i
return []