Description
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 exactlyone solution, and you may not use the same element twice.
Example:
1
2
3
4
| Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
|
思路0
從給定數組中找到兩個元素的和為指定值的兩個索引，最暴力的做法就是循環兩次，復雜度為$0(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; ++i) {
for (int j = i + 1; j < nums.length; ++j) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return null;
}
}
|
思路1
用HashMap為存儲，鍵為目標值減去當前元素的值，索引為值。比如 i = 0 時，此時首先要判斷 nums[0] = 2 是否在 map 中，如果不存在，那麽插入鍵值對 key = 9 - 2 = 7, value = 0，之後當 i = 1 時，此時判斷 nums[1] = 7 key = 9 - 7 = 2,value = 1 key =2 已存在於 map 中，那麽取出該 value = 0 作為第一個返回值，當前 i 作為第二個返回值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| import java.util.HashMap;
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++){
int key = target - nums[i];
if (hashMap.containsKey(key)){
return new int[]{hashMap.get(key), i};
}
hashMap.put(nums[i],i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
|
####
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
numberIndexDict = {}
for i, x in enumerate(nums):
y = target - x
if y in numberIndexDict:
return [numberIndexDict[y], i]
numberIndexDict[x] =
|
