【leetcode】#1 Two Sum【Hash】【Easy】
程序员文章站
2022-07-15 14:30:52
...
1. Two Sum
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].
题目大意
给出一个整数数组,你需要返回满足数组中相加等于一个目标值的两个数的索引,题目假设给出的数据必有一个解,并且你不能用同一个元素两次
解题思路
利用Hash的思想,给每个输入的值计数,对数组中的每个数判断是否有数相加等于目标值,若有则找到目标值的位置,返回这两个位置。
AC代码
#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<int, int> mp;
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
for(int i = 0; i < nums.size(); i++) {
mp[nums[i]]++; //记录每个值出现的次数
}
for (int j = 0; j < nums.size(); ++j) {
if(mp[target - nums[j]] >= 1) { //若两数相加等于target的值存在
if(target - nums[j] == nums[j] && mp[nums[j]] == 1) continue; //防止一个数被用两次
int x = j + 1;
while (nums[x] != target - nums[j]) x++; //寻找另一个数的位置
ans.push_back(j);
ans.push_back(x);
break;
}
}
return ans;
}
int main() {
vector<int> test = {2, 7, 11, 15};
vector<int> ans = twoSum(test, 9);
for(int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
return 0;
}
推荐阅读
-
【LeetCode】Two Sum & Two Sum II - Input array is sorted & Two Sum IV - Input is a BST
-
LeetCode - 1. Two Sum(8ms)
-
LeetCode_#1_两数之和 Two Sum_C++题解
-
LeetCode(62)-Two Sum
-
LeetCode:Two Sum浅析
-
[LeetCode] 1. Two Sum 两数之和
-
【leetcode】#1 Two Sum【Hash】【Easy】
-
LeetCode 454. 4Sum II (Hash Table)
-
LeetCode 1 Two Sum (hash)
-
[leetcode]1. Two Sum