1. 两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

1
2
3

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1 2	`输入：nums = [3,2,4], target = 6 输出：[1,2]`

示例 3：

1 2	`输入：nums = [3,3], target = 6 输出：[0,1]`

提示：

\(2\) \(≤\) \(nums.length\) \(≤\) \(10^4\)
\(-10^9\) \(≤\) \(nums[i]\) \(≤\) \(10^9\)
\(-10^9\) \(≤\) \(target\) \(≤\) \(10^9\)
只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 \(O(n^2)\) 的算法吗？

思路

首先说一个\(O(n^2)\)的做法。在遍历到每一个数的时候，再遍历一遍数组，找到相加等于target的时候，返回两数坐标。注意，两下标不能相等

// C++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans(2);
        for (int i = 0; i < nums.size(); i++)
            for (int j = 0; j < nums.size(); j++) {
                if (i == j) continue;

                if (nums[i] + nums[j] == target) {
                    ans[0] = i;
                    ans[1] = j;
                }
            }

        return ans;
    }
};

仔细观察，能不能找到一种在\(O(1)\)的复杂度内找到当前数在整个数组中对应的数，使它们的和为target？

答案是可以。快速查找可以联想到建立哈希表。

通过遍历数组，查找哈希表内是否存在与之对应的和为target的数。

若存在，break；
若不存在，将当前数插入到哈希表内。

由于不用对哈希表排序，所以使用无序哈希（查找为 \(O(1)\) ），因此总时间复杂度为\(O(n)\)

代码

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp; // key存数的值，value存数的下标
        vector<int> res(2);
        for (int i = 0; i < nums.size(); i++) {
            if (mp.count(target - nums[i])) {
                res[0] = mp[target - nums[i]];
                res[1] = i;
                break;
            }
            mp[nums[i]] = i;
        }
        return res;
    }
};