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].题目内容： 给出一个整数数组nums，和一个target数，返回这个数组中加起来的和为target的两个数的下标。假定每个输入都有解，而且每个数字只能使用一次。
解题思路： 解决这道题的一个简单的思路是遍历数组，然后查找数组是否存在与当前位置的元素x加起来的和等于target的元素y，如果有就返回这个元素y和元素x的下标。 因为这里涉及到从元素值到下标的映射，所以我用到了一个unordered_map来实现这个功能，将元素值作为key，该元素的下标作为value。 首先初始化一个空的unordered_map，从头开始遍历数组，求出要找的元素值为target - nums[i]，
如果在unordered_map找不到这个值，那么先将当前元素的值和下标都加入进这个unordered_map，其中key为元素值，value为下标。如果在unordered_map找到这个值，说明数组中存在这个值，那么就可以将找到的元素下标和当前元素的下标放到一个vector里面返回。因为把下标都存放都vector里面就存在一个下标顺序的问题，应该哪个下标放前面？因为题目也没有明确规定个，所以我是将先出现的下标放前面。因为从unordered_map里面找到的元素肯定是比当前元素出现得早的，这些元素在遍历到当前元素之前就被遍历过并且插入到unordered_map里面了，所以我首先将unordered_map里面找到的元素下标放进vector，再把当前元素的下标放进vector。
代码：
#include <iostream>#include <vector>#include <unordered_map>using namespace std;class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> result; unordered_map<int, int> un_map; for (int i = 0; i < nums.size(); i++) { int needFound = target - nums[i]; if (un_map.find(needFound) == un_map.end()) { un_map[nums[i]] = i; } else { result.push_back(un_map[needFound]); result.push_back(i); return result; } } return result; }};int main() { int array[] = {3, 2, 4}; int count = sizeof(array) / sizeof(int); vector<int> nums(array, array + count); int target = 6; Solution sln; vector<int> result = sln.twoSum(nums, target); cout << result[0] << " " << result[1] << endl; return 0;}新闻热点
疑难解答
