题目描述

原题链接：1. 两数之和

一、采用Hash表

目标是求两数之和的下标，采用unordered_map设置Key为求和之值，Value为对应元素下标。每次先查找之前是否有另一个数在存储中，若在则返回答案，若不在则加入到其中。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> record;
        for(int i = 0; i < nums.size(); i++) {
            auto it = record.find(target - nums[i]);
            if(it != record.end()) {
                return {it->second, i};     // 找到返回第一个下标和第二个下标
            }
            // record.insert(pair<int, int>(nums[i], i));
            record[nums[i]] = i;    // 注意：因为可能出现二倍的数为目标之和，为避免仅有一个数而提前判定已在存储中，因此需要先判定再存储Key-Value。
        }
        return {};      // 未找到返回{}
    }
};

时间复杂度：$O(n)$
空间复杂度：$O(n)$

二、排序+双指针

可以下排序，然后再用双指针方式，设置一个首指针，设置一个尾指针，利用数组中的单调性遍历。直至找到nums[i] + nums[j] == target

AcWing 800. 数组元素的目标和