本文共 2443 字，大约阅读时间需要 8 分钟。

题目链接：

这一题的意思是：在一个数组中找到两个数，这两个数的和是target。需要返回这两个数的下标，下标需要按照在原始数组中的顺序，注意：返回的下标是从1开始，不是从0开始。

方法一：最简单想到的方法是：两重循环，一对一对比较，这个简单，就不写了。

方法二：使用hash表做，思想：hash表用于保存那些元素所在的位置，每次遇到一个num，去判断target-num是不是在hash表中，如果在，那么说明找到了，直接返回，不在的话说明还没有找到，那么需要加入hash表，然后继续。

需要注意：因为允许存在相等的元素，那么每次加入hash表的时候需要判断是不是已经存在，如果已经存在这个数，那么不需要再次加入，因为我们保存最小的下标就OK！Ps:由于题目说只存在一种答案，那么这个考虑其实也是多余的，但是考虑下还是好的！

代码如下：

class Solution {public:    vector
   
     twoSum(vector
    
      &numbers, int target) {        vector
     
       res;        // 首先构建一个位置映射表        //        unordered_map
      
        ele_location;        int i, n = numbers.size();        for (i = 0; i < n; ++i){            // 找到和值，那么就得到答案了            //            if (ele_location.find(target-numbers[i]) != ele_location.end()){                res.push_back(ele_location[target-numbers[i]] + 1);                res.push_back(i+1);                return res;            }            else// 注意下面这个判断：如果不存在那么进入hash表，否则不用，因为保存最小的下标就OK！                if (ele_location.find(numbers[i]) == ele_location.end())                    ele_location[numbers[i]] = i;        }        return res;    }};
      
     
    
   

方法三：我们先将nums进行排序，然后按照有序序列方法来找两个数之和，这个是常见的题，然后将找到的两个数在原始的数组中找到两个数的位置就OK！不过需要注意：如果找到两个元素是一样的，例如2+2=4，我们首先找到第一个2，当然是OK的，但是找第二个，那么我们找到的还是第1个2位置，所有我们这个时候，需要随便做一下处理，例如处理完第一个数之后，让num++就行了，这个随便你！

代码：

class Solution {public:    vector
   
     twoSum(vector
    
      &numbers, int target) {        vector
     
       res;        vector
      
        bak = numbers;        int i, j, n = numbers.size();        sort(numbers.begin(), numbers.end());        i = 0;        j = n - 1;        while (i < j){            if (numbers[i] + numbers[j] == target){                int k, x, y;                for (k = 0; k < n; ++k)                    if (numbers[i] == bak[k]){                        x = k;                        // 注意，防止和之前的元素相等！                        //                        bak[k]++;                        break;                    }                for (k = 0; k < n; ++k)                    if (numbers[j] == bak[k]){                        y = k;                        break;                    }
       		// 注意：下标从1开始哦！                res.push_back(x > y ? y + 1 : x + 1);                res.push_back(x > y ? x + 1 : y + 1);                return res;            }            if (numbers[i] + numbers[j] < target)                ++i;            else                --j;        }        return res;    }};
      
     
    
   

转载地址：http://gaaci.baihongyu.com/