问题:
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
思路:
(1)使用数据结构map
(2)不着急把所有数据放到map中去,首先查找target-numbers[i]值在不在map中,在说明找到了,第一个index是找到的map中保存的index,第二个index是当前的i;
(3)如果target-numbers[i]值没找到,并且当前的numbers[i]不在map中,将当前值加入map中。
代码:
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> index;
map<int, int> mp;
map<int, int>::iterator iter;
for(int i = 0; i != numbers.size(); ++i) {
iter = mp.find(target-numbers[i]);
if(iter != mp.end() ) {
int start = mp.find(target-numbers[i])->second;
int end = i + 1;
index.push_back(start);
index.push_back(end);
return index;
} else {
map<int, int>::iterator it = mp.find(numbers[i]);
if(it == mp.end()) {
mp[numbers[i]] = i + 1;
}
}
}
}
};
分享到:
相关推荐
js代码-1. 两数之和 [简单] https://leetcode-cn.com/problems/two-sum
leetcode-1-Two-Sum 这是我在 Github 的第一天。 我只是 AC leetcode 中的第一个问题。 从现在开始,我将使用Github在leetcode中记录我的生活。 我擅长 C++,但对 java 和 Python 不是很专业,我将使用最流行的 3 种...
Two-Sum leetcode两数之和代码 题目描述:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组...
Two-Sum(两数和问题) 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下 可以假设每种输入只会对应一个答案。但是,不能重复利用这个数组中同样的...
swift代码-1. 两数之和 [简单] https://leetcode-cn.com/problems/two-sum
java代码-1. 两数之和 [简单] https://leetcode-cn.com/problems/two-sum
c代码-1. 两数之和 [简单] https://leetcode-cn.com/problems/two-sum
leetcode167 LeetCode167_Two-Sum-II 给定一个目标target,再数组中找到两个数,使其和为target,并返回对应数组中索引(从1开始)
js代码-给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值...链接:https://leetcode-cn.com/problems/two-sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
matlab开发-sumoftwo向量。可视化两个向量的总和
Two Sum. Memory Usage: 5.8 MB, less than 99.36% of C online submissions for Two Sum. #1. Two Sum Given an array of integers nums and an integer target, return indices of the two numbers such that they...
twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的答案(index1 和 index2)不是从零开始的。 您可以假设每个输入都只有一个解决方案。 输入:number={2, 7, 11, ...