1. Two Sum

妖狐艹你老母 2022-04-18 06:33 294阅读 0赞

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:

  1. Given nums = [2, 7, 11, 15], target = 9,
  3. Because nums[0] + nums[1] = 2 + 7 = 9,
  4. return [0, 1].

方法：使用一个map，该map以原数组中的值为键，下标为值。扫描数组nums中第i个元素时，查看target-nums[i]是否在map中，若在则可得到结果。 

  1. class Solution {
  2. public:
  3.     vector<int> twoSum(vector<int>& nums, int target) {
  4.        vector<int> result;
  5.      map<int, int> dic;
  6.     for (int i = 0; i < nums.size(); i++)
  7.     {
  8.         if (dic.find(target-nums[i]) != dic.end())
  9.         {
  10.             result.push_back(dic[target - nums[i]]);
  11.             result.push_back(i);
  12.             return result;
  13.         }
  14.         else
  15.         {
  16.             dic[nums[i]] = i;
  17.         }
  18.     }
  19.     return result; 
  20.     }
  21. };

发表评论

表情：
评论列表 （有 0 条评论，294人围观）

还没有评论，来说两句吧...

相关阅读