1 Tow Sum
程序员文章站
2024-02-29 10:46:46
...
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.
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
解题代码如下:
#include<stdio.h>
#include <iostream>
#include <vector>
#include<algorithm>
#include<functional>
#include<tr1/unordered_map>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int> &numbers,int target){
std::tr1::unordered_map<int,int> hash;
vector<int> result;
for(int i=0;i<numbers.size();i++){
int numberToFind = target-numbers[i];//用目标值依次减去向量中的元素得到剩余值
if(hash.find(numberToFind)!=hash.end()){//判断剩余值是否在hash表中出现,如果出现则获取其对应的键值
result.push_back(hash[numberToFind]);
result.push_back(i);
return result;
}
hash[numbers[i]]=i;//不在表中则加入表中
}
return result;
}
};
int main()
{
Solution s;
vector<int> vec_A;
int target,c,n;
cin>>target;
cin>>n;
for(int i=0;i<n;i++){
cin>>c;
vec_A.push_back(c);
}
vector<int> result = s.twoSum(vec_A,target);
cout<<result[0]<<result[1]<<endl;
return 0;
}
整个思路很简单啊,将vector转换成一个值和下表对应的hash表,然后用目标值依次减去vector中的值得到剩余值,判断剩余值是否在hash表中,有则返回。
上一篇: 作业:大数据之Sqoop的使用