两数之和

题目链接

注意事项

• 1️⃣有且仅有一个正确答案。
• 2️⃣每个数只能使用一次。
• 3️⃣返回的是下标

解法一：两个for循环，找到了直接返回即可。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        // 没有找到
        return {-1, -1};
    }
};

• 时间复杂度：O(n^2)

解法二：先排序，然后左指针指向第一个数，右指针指向最后一个数，如果两数之和大于target，则右指针往左动，如果两数之和小于target，则左指针往右动。

• 不好意思，这方法不行，因为返回的是下标！排序后，下标混乱了。

解法三：从左往右便利，我们在便利到i下标，也就是nums[i]时，我们想知道，之前便利过的数有没有target - nums[i]，如果有，那么就直接返回即可。所以，我们使用一个哈希表，存放已经便利过的数。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        map<int, int> preNums;    // 数字-下标
        for (int i = 0; i < n; ++i) 
        {
            if (preNums.count(target - nums[i]) != 0) {    // 找到了
                return {preNums[target - nums[i]], i};
            }
            // 没找到   保存信息，供后面的便利使用
            preNums[nums[i]] = i;
        }
        return {-1, -1};
    }
};