第一题： Two Sum

╰半橙微兮° 2022-08-06 17:22 126阅读 0赞

题目链接：[题目链接][Link 1]

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

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

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

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

代码如下：

class Solution {
    public:
        vector<int> twoSum(vector<int> &numbers, int target) {
            vector<int> res;
    
            // 首先构建一个位置映射表
            //
            unordered_map<int, int> 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<int> twoSum(vector<int> &numbers, int target) {
            vector<int> res;
    
            vector<int> 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;
                        }
    <span style="white-space:pre">		</span>// 注意：下标从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;
        }
    };

[Link 1]: https://oj.leetcode.com/problems/two-sum/