BM50. [两数之和]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM50. 两数之和

https://www.nowcoder.com/practice/20ef0972485e41019e39543e8e895b7f?tpId=295&sfm=discuss&channel=nowcoder

题中可以看出：

• 必定存在唯一解，不用考虑特殊情况
• 返回的下标是数组下标加1
  最能想到的办法莫过于暴力解决，直接遍历两层循环，相加与target比较，若相同则跳出循环。

方法一：暴力比较法

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res;
        for(int i = 0; i < numbers.size(); i++)  //暴力循环两边
            for(int j = i + 1; j < numbers.size(); j++){
                if(numbers[i] + numbers[j] == target){   //相加等于target即找到唯一解
                    res.push_back(i + 1); //因下标从1开始
                    res.push_back(j + 1);
                    break;
                }
             }
        return res;
    }
};

复杂度分析：

• 时间复杂度：O(n^2)，两层for循环
• 空间复杂度：O(1)，没有使用额外空间

方法二：哈希表法

有了暴力比较法的加法比较，反方向也有减法比较。减法比较利用的是哈希表。

具体做法：
遍历整个数组，在遍历的过程中查找哈希表是否存在target与当前数字的差，若没有，则将当前数字加入哈希表中，如果存在，则返回哈希表中对应的下标。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res;
        unordered_map<int, int> hash; //创建hash表,两元组分别表示值、下标
        //在hash表中查找target-numbers[i]
        for(int i = 0; i < numbers.size(); i++){
            int temp = target - numbers[i];
            if(hash.find(temp) == hash.end()){ //若是没找到，将此信息计入hash表
               hash[numbers[i]] = i;
            }
            else{
               res.push_back(hash[temp] + 1);   //hash表中记录的是之前的数字，所以该索引比当前小
               res.push_back(i + 1);
               break;
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：O(n)，仅一个for循环
• 空间复杂度：O(n)，使用的哈希表最大空间为O(n)