LeetCode 1. Two Sum

希望这次能刷过100题……

Question

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[0] + nums[1] = 2 + 7 = 9,
return [0, 1].


Solution

EN

The approach is using hash map to solve the problem. While iterating through the array, the value and corresponding index is stored into hash map. Whilst at the same time, the complementary value of the current index is also checked. If the value of complementary value exists in hash map, just directly return the index of complementary value and current index.


CN

解法是使用Hash Map去解这道题。遍历整个列表的同时,将值作为键,对应的序号作为值存入Hash Map中。遍历时,计算当前值和的目标值的差,记作补数(complementary),并在Hash Map中寻找补数是否存在。如果补数存在,就直接返回补数对应的序号和当前序号。


Code

Java

1
2
3
4
5
6
7
8
9
10
11
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complementary = target - nums[i];
if (map.containsKey(complementary)) {
return new int[]{map.get(complementary), i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No solution");
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dic = {}
for i, n in enumerate(nums):
if n in dic:
return [dict[n], i]
dic[target-n] = i

For more enumerate, checkout Enumerate() in Python


Complexity Analysis

  • Time Complexity: since only need to traverse the whole list containing element once; and the look up in the table costs time.

  • Space Complexity: . At the worst case, if the pair of index does not exist, then all elements are required to be stored in the hash map, which at most is elements.


Reference

Solution

-------The end of this article  Thank you for your reading-------
0%