给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
用两个for循环遍历所有可能，时间复杂度为O(n^2)。
1 class Solution { 2 public: 3 vector<int> twoSum(vector<int>& nums, int target) { 4 int i, j; 5 for(i = 0; i < nums.size()-1; i++) { 6 for(int j = i + 1; j < nums.size(); j++) { 7 if((nums[i] + nums[j]) == target){ 8 return{i, j}; 9 } 10 } 11 } 12 return {}; 13 } 14 };
在容器中插入元素的同时，检查容器中是否存在差值。
1 class Solution { 2 public: 3 vector<int> twoSum(vector<int>& nums, int target) { 4 map<int, int> temp; // map<key, value> 5 vector<int> current(2, 0); // 存储结果，初始化一个大小为2，值为0的容器。 6 for(int i=0;i<nums.size();i++){ 7 if(temp.count(target-nums[i])>0){ // 在temp中查找target-nums的个数, 8 // 大于0表示 9 current[0] = temp[target-nums[i]]; // 存储第一个数的key 10 current[1] = i; // 存储第二个key 11 break; 12 } 13 temp[nums[i]] = i; // 将前面所有不符合条件的都放入map, 14 // key为nums值，value为下标。 15 } 16 return current; 17 } 18 };
努力去爱周围的每一个人，付出，不一定有收获，但是不付出就一定没有收获！ 给街头卖艺的人零钱，不和深夜还在摆摊的小贩讨价还价。愿我的博客对你有所帮助(*^▽^*)(*^▽^*)！
如果客官喜欢小生的园子，记得关注小生哟，小生会持续更新(#^.^#)(#^.^#)。
原文：https://www.cnblogs.com/haifwu/p/13706316.html