力扣Leetcode：1. 两数之和（C++、Python、Java）
题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
题解
用空间换时间，使用一个字典，键为元素值，值为元素下标。
遍历数组中的所有元素，对于nums[i]，只需要检查字典中是否存在target-nmums[i]即可。
以下分别使用了C++、Python、Java实现了这一算法，主要在于不同语言对于map的使用方式。个人感觉Python最为简单易用。
Python代码
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dic={}
for i in range(len(nums)):
if target-nums[i] in dic and i != dic[target-nums[i]]:
return [dic[target-nums[i]],i]
dic[nums[i]]=i
return [None,None]
Java代码
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> hashMap=new HashMap<Integer, Integer>();
for(int i=0; i<nums.length; i++) {
hashMap.put(nums[i],i);
}
for(int i=0; i<nums.length; i++) {
if(hashMap.containsKey(target-nums[i])) {
if(i!=hashMap.get(target-nums[i]))
return new int[]{i,hashMap.get(target-nums[i])};
}
}
return new int[]{0,0};
}
}
C++代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
vector<int> rs;
for(int i=0; i<nums.size(); i++) {
if(m.find(target-nums[i])!=m.end() && m[target-nums[i]]!=i) {
rs.push_back(m[target-nums[i]]);
rs.push_back(i);
return rs;
} else {
m[nums[i]]=i;
}
}
return rs;
}
};