两数之和，不一样的
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
暴力：不要说了。O（n*n）
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int i,j; for(i=0;i<nums.size()-1;i++) { for(j=i+1;j<nums.size();j++) { if(nums[i]+nums[j]==target) { return {i,j}; } } } return {i,j}; }; };
关键是O(n)做出来
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { map<int,int> a;//提供一对一的hash vector<int> b(2,-1);//用来承载结果，初始化一个大小为2，值为-1的容器b for(int i=0;i<nums.size();i++) { if(a.count(target-nums[i])>0) { b[0]=a[target-nums[i]]; b[1]=i; break; } a[nums[i]]=i;//反过来放入map中，用来获取结果下标 } return b; }; };
投递阿里国际数字商业集团等公司10个岗位 >
查看3道真题和解析