-
Notifications
You must be signed in to change notification settings - Fork 0
/
0001. Two Sum
38 lines (32 loc) · 1.45 KB
/
0001. Two Sum
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
28
29
30
31
32
33
34
35
36
37
38
'''
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
'''
class Solution: #One-pass Hash Table T:O(n) S:O(n)
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = {} # store bIndex as value, a or b as keys
for bIndex, b in enumerate(nums):
# dic[b] = bIndex # index不能先放入dic,因为会与自己相等
a = target - b
if a in dic:
return [bIndex, dic[a]]
dic[b] = bIndex # index最后放入dic,为下一轮查字典提供index
if __name__ == "__main__":
print(Solution().twoSum([2, 7, 11, 15], 9));
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
// In case there is no solution, we'll just return null
return null;
}
}