1. 两数之和
题目描述
输入一个整数数组 nums 和一个整数 target。数组中恰好有两个位置上的数相加等于 target，找出这两个位置。
返回由这两个下标组成的数组。两个下标必须不同，即同一个元素不能用两次。下标的先后顺序不限。
题目保证答案存在且唯一。
示例 1
输入：nums = [2,7,11,15], target = 9 输出：[0,1]
解释：nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0,1]。
示例 2
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3
输入：nums = [3,3], target = 6 输出：[0,1]
解释：两个 3 位于不同下标，可以组成答案。
数据范围
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9- 答案唯一。
进阶：能否设计时间复杂度低于 O(n^2) 的算法？
解题思路：哈希表（一次遍历）
从左到右扫描。当前值 x 需要的补数是 target-x；先在哈希表中查补数，找到就返回，再把 x 及其下标登记。这样每个元素只访问一次。
为什么正确
扫描到 i 时，seen 保存了下标小于 i 的值；若答案右端点是 i，补数一定能在 seen 中找到。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
不要先覆盖当前值再查找，否则同一个元素可能被错误地使用两次。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def twoSum(self, nums, target):
seen = {}
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return []class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) {
return new int[]{seen.get(need), i};
}
seen.put(nums[i], i);
}
return new int[0];
}
}class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> seen;
for (int i = 0; i < (int)nums.size(); i++) {
int need = target - nums[i];
if (seen.count(need)) {
return {seen[need], i};
}
seen[nums[i]] = i;
}
return {};
}
};func twoSum(nums []int, target int) []int {
seen := map[int]int{}
for i, x := range nums {
need := target - x
if j, ok := seen[need]; ok {
return []int{j, i}
}
seen[x] = i
}
return []int{}
}var twoSum = function(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) {
return [seen.get(need), i];
}
seen.set(nums[i], i);
}
return [];
};function twoSum(nums: number[], target: number): number[] {
const seen = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) {
return [seen.get(need)!, i];
}
seen.set(nums[i], i);
}
return [];
};其他解法
哈希表用 O(n) 空间换来一次遍历；暴力枚举不占空间但是 O(n²)；排序 + 双指针居中，并且是 n 数之和系列题的通用模板。
解法 2：暴力枚举 时间 O(n²)，空间 O(1)
枚举每一对下标 i < j，检查 nums[i] + nums[j] 是否等于 target。第一次命中就返回这对下标。
代码最短，不需要额外空间。n 达到 10⁴ 时要做约 5×10⁷ 次比较，比哈希表慢很多。适合作为第一版思路和对拍基准。
class Solution:
def twoSum(self, nums, target):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
}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 {};
}
};func twoSum(nums []int, target int) []int {
n := len(nums)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if nums[i]+nums[j] == target {
return []int{i, j}
}
}
}
return []int{}
}var twoSum = function(nums, target) {
const n = nums.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
};function twoSum(nums: number[], target: number): number[] {
const n = nums.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
};解法 3：排序 + 双指针 时间 O(n log n)，空间 O(n)
把下标按数值排序。左指针从最小值出发，右指针从最大值出发。两数之和偏小就右移左指针，偏大就左移右指针，相等时返回两个原始下标。
排序会打乱位置，所以必须排序下标而不是直接排序数值。比哈希表多一个 log n，但同样的套路可以推广到三数之和、四数之和。
class Solution:
def twoSum(self, nums, target):
idx = sorted(range(len(nums)), key=lambda k: nums[k])
lo, hi = 0, len(idx) - 1
while lo < hi:
s = nums[idx[lo]] + nums[idx[hi]]
if s == target:
return sorted([idx[lo], idx[hi]])
if s < target:
lo += 1
else:
hi -= 1
return []class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
Integer[] idx = new Integer[n];
for (int k = 0; k < n; k++) idx[k] = k;
Arrays.sort(idx, (a, b) -> Integer.compare(nums[a], nums[b]));
int lo = 0, hi = n - 1;
while (lo < hi) {
int s = nums[idx[lo]] + nums[idx[hi]];
if (s == target) {
return new int[]{Math.min(idx[lo], idx[hi]), Math.max(idx[lo], idx[hi])};
}
if (s < target) lo++;
else hi--;
}
return new int[0];
}
}class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
vector<int> idx(n);
for (int k = 0; k < n; k++) idx[k] = k;
sort(idx.begin(), idx.end(), [&](int a, int b) { return nums[a] < nums[b]; });
int lo = 0, hi = n - 1;
while (lo < hi) {
int s = nums[idx[lo]] + nums[idx[hi]];
if (s == target) {
return {min(idx[lo], idx[hi]), max(idx[lo], idx[hi])};
}
if (s < target) lo++;
else hi--;
}
return {};
}
};func twoSum(nums []int, target int) []int {
n := len(nums)
idx := make([]int, n)
for k := range idx {
idx[k] = k
}
sort.Slice(idx, func(a, b int) bool { return nums[idx[a]] < nums[idx[b]] })
lo, hi := 0, n-1
for lo < hi {
s := nums[idx[lo]] + nums[idx[hi]]
if s == target {
i, j := idx[lo], idx[hi]
if i > j {
i, j = j, i
}
return []int{i, j}
}
if s < target {
lo++
} else {
hi--
}
}
return []int{}
}var twoSum = function(nums, target) {
const idx = nums.map((_, k) => k).sort((a, b) => nums[a] - nums[b]);
let lo = 0, hi = idx.length - 1;
while (lo < hi) {
const s = nums[idx[lo]] + nums[idx[hi]];
if (s === target) {
return [Math.min(idx[lo], idx[hi]), Math.max(idx[lo], idx[hi])];
}
if (s < target) lo++;
else hi--;
}
return [];
};function twoSum(nums: number[], target: number): number[] {
const idx = nums.map((_, k) => k).sort((a, b) => nums[a] - nums[b]);
let lo = 0, hi = idx.length - 1;
while (lo < hi) {
const s = nums[idx[lo]] + nums[idx[hi]];
if (s === target) {
return [Math.min(idx[lo], idx[hi]), Math.max(idx[lo], idx[hi])];
}
if (s < target) lo++;
else hi--;
}
return [];
};