跳转至

两数之和

力扣 1

给定一个整数数组 nums，请你在这个数组中寻找出两个不同的整数 x 和 y，使得 x + y = target.

题目保证每个测试样例必有解.

完善代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

    }
};

数据范围

\(2 \leq\) nums.size() \(\leq 10 ^ 4\)

\(-10^9 \leq\) nums[i]、target \(\leq 10 ^ 9\)

排序、二分法、左右指针 往正确答案的方向 靠拢

代码参考 
class Solution {
public:
    vector<vector<int>> tp;

    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i ++) tp.push_back({nums[i], i});
        auto cmp = [](const vector<int>& a, const vector<int>& b)->bool { return a[0] < b[0]; };
        sort(tp.begin(), tp.end(), cmp);
        int i = 0, j = tp.size() - 1;
        while (i < j)
        {
            int t = tp[i][0] + tp[j][0];
            if (t > target) j --;
            else if (t < target) i ++;
            else return {tp[i][1], tp[j][1]};
        }
        return {};
    }
};

借助 map

代码参考 
class Solution {
public:
    map<int, int> mp;
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i ++)
        {
            auto t = mp.find(target - nums[i]);
            if (t != mp.end()) return {i, t->second};
            mp.insert({nums[i], i});
        }
        return {};
    }
};