两数之和

题目要求

给定一个整数数组 nums 和一个整数目标值 target，需要找到数组中两个数，使得这两个数的和等于 target。然后返回这两个数在数组中的下标。

题目的限制条件如下：

每种输入只对应一个答案，即数组中不会有多组不同的数对能够满足和为 target 的条件。
同一个元素不能在答案中重复出现，即不能使用数组中同一个位置的数两次。
返回的答案不限制顺序。

解题思路

解决这个问题的关键是如何有效地查找数组中是否存在两个数，它们的和为 target。以下是解题的步骤：

哈希表法：这是一种时间复杂度为 O(n) 的解法。可以通过一次遍历数组，边遍历边记录已经访问过的数字及其下标，来检查是否存在一个值与当前遍历到的数字相加等于 target。
- 初始化一个哈希表（通常是一个字典或者映射结构）。
- 遍历数组 nums，对于每个元素 x，计算 complement = target - x。
- 检查 complement 是否已经在哈希表中：
  - 如果在，那么找到了一对答案，返回 x 的下标和 complement 的下标。
  - 如果不在，将 x 及其下标存入哈希表中。
- 如果遍历结束都没有找到答案，则说明不存在满足条件的两个数。
双指针法：如果数组是有序的，还可以使用双指针法。首先对数组进行排序，然后使用两个指针分别指向数组的开头和结尾，根据两指针所指元素之和与 target 的比较，移动指针，直到找到一对和为 target 的元素。
- 对数组 nums 进行排序。
- 初始化两个指针，left 指向数组开始，right 指向数组末尾。
- 当 left < right 时，进行以下操作：
  - 如果 nums[left] + nums[right] == target，返回这两个数的下标。
  - 如果 nums[left] + nums[right] < target，则 left 指针右移，因为数组是有序的，右移可以增加和的值。
  - 如果 nums[left] + nums[right] > target，则 right 指针左移，因为数组是有序的，左移可以减少和的值。
- 如果没有找到答案，说明不存在满足条件的两个数。

注意：使用双指针法时，排序会改变元素的原始下标，因此需要额外的步骤来找回原始下标，或者在排序前就记录下每个元素的原始下标。

在实际应用中，由于题目要求不能重复使用同一个元素，哈希表法更为直接和高效，通常作为首选方法。

Golang 版本

package main

import "fmt"

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    for i, num := range nums {
        if j, ok := numMap[target-num]; ok {
            return []int{j, i}
        }
        numMap[num] = i
    }
    return nil
}

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9
    result := twoSum(nums, target)
    fmt.Println(result) // 输出 [0 1]，因为 nums[0] + nums[1] = 2 + 7 = 9
}

这段代码实现了哈希表法来解决问题。它创建了一个名为 numMap 的哈希表来存储数组元素值到它们索引的映射。在遍历数组的过程中，对于每个元素，代码会检查 target 减去当前元素值的结果是否已经在 numMap 中。如果是，就找到了一对符合条件的元素，并返回它们的索引。如果遍历结束都没有找到，函数返回 nil。

C++版本

#include <iostream>
#include <vector>
#include <unordered_map>

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> numMap;
    for (int i = 0; i < nums.size(); ++i) {
        auto it = numMap.find(target - nums[i]);
        if (it != numMap.end()) {
            return {it->second, i};
        }
        numMap[nums[i]] = i;
    }
    return {};
}

int main() {
    std::vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    std::vector<int> result = twoSum(nums, target);
    std::cout << "Index1: " << result[0] << ", Index2: " << result[1] << std::endl;
    return 0;
}

这段 C++代码使用了 std::unordered_map 来实现哈希表，用于存储数组元素值和它们的索引。在遍历数组的过程中，对于每个元素，代码会在哈希表中查找 target 减去当前元素值的结果。如果找到了，就返回一个包含两个索引的向量。如果没有找到符合条件的元素对，函数返回一个空的向量。在 main 函数中，我们定义了一个示例数组和目标值，调用 twoSum 函数，并打印出结果。

Python 版本

def two_sum(nums, target):
    num_dict = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_dict:
            return [num_dict[complement], i]
        num_dict[num] = i
    return []

# 测试代码
if __name__ == "__main__":
    nums = [2, 7, 11, 15]
    target = 9
    print(two_sum(nums, target))  # 输出 [0, 1]，因为 nums[0] + nums[1] = 2 + 7 = 9

这段 Python 代码实现了一个 two_sum 函数，它使用字典 num_dict 来存储遍历过程中每个数字的索引。在遍历数组 nums 的过程中，对于每个数字，它会计算与当前数字相加能得到 target 的补数（complement），然后检查这个补数是否已经在字典中。如果是，就返回一个包含两个索引的列表。如果遍历结束都没有找到符合条件的数字对，函数返回一个空列表。在主函数中，我们定义了一个示例数组和目标值，调用 two_sum 函数，并打印出结果。

Java 版本

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[] { numMap.get(complement), i };
            }
            numMap.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = solution.twoSum(nums, target);
        System.out.println("Index1: " + result[0] + ", Index2: " + result[1]); // 输出 Index1: 0, Index2: 1
    }
}

这段 Java 代码定义了一个 Solution 类，其中包含一个 twoSum 方法来解决两数之和的问题。它使用了一个 HashMap 来存储遍历过程中每个数字的索引。在遍历数组 nums 的过程中，对于每个数字，它会计算与当前数字相加能得到 target 的补数（complement），然后检查这个补数是否已经在 HashMap 中。如果是，就返回一个包含两个索引的数组。如果遍历结束都没有找到符合条件的数字对，方法会抛出一个异常。main 方法用于测试 twoSum 方法，定义了一个示例数组和目标值，调用 twoSum 方法，并打印出结果。

Rust 版本

use std::collections::HashMap;

fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut num_map = HashMap::new();
    for (i, &num) in nums.iter().enumerate() {
        match num_map.get(&(target - num)) {
            Some(&index) => return vec![index as i32, i as i32],
            None => num_map.insert(num, i),
        };
    }
    vec![]
}

fn main() {
    let nums = vec![2, 7, 11, 15];
    let target = 9;
    let result = two_sum(nums, target);
    println!("Index1: {}, Index2: {}", result[0], result[1]);
}

这段 Rust 代码实现了一个 two_sum 函数，它使用了一个 HashMap 来存储遍历过程中每个数字的索引。在遍历 Vec<i32> 类型的数组 nums 的过程中，对于每个数字，它会计算与当前数字相加能得到 target 的补数，并检查这个补数是否已经在 HashMap 中。如果是，就返回一个包含两个索引的 Vec<i32>。如果遍历结束都没有找到符合条件的数字对，函数返回一个空的 Vec<i32>。

main 函数用于测试 two_sum 函数，定义了一个示例数组和目标值，调用 two_sum 函数，并打印出结果。注意，Rust 使用模式匹配（match）来处理 Option 类型，这是 Rust 中处理可能不存在值的惯用方式。

总结

上述解法采用了哈希表来优化查找过程，以实现在数组中找到两个数，它们的和等于目标值 target 的问题。具体步骤如下：

初始化一个哈希表（在 Go 中是map，在 Rust 中是HashMap）来存储数组中每个元素的值和它们对应的索引。
遍历数组中的每个元素：
- 对于每个元素，计算它和目标值 target 之间的差值。
- 检查这个差值是否已经在哈希表中：
  - 如果差值存在，那么当前元素和哈希表中的差值对应的元素就是我们要找的两个数。返回它们的索引。
  - 如果差值不存在，将当前元素及其索引存入哈希表中。
如果遍历结束后没有找到符合条件的元素对，则返回一个空数组或抛出异常（取决于语言特性）。

这种方法的时间复杂度为 O(n)，因为它只需要遍历数组一次。空间复杂度也为 O(n)，因为最坏的情况下，可能需要存储数组中所有元素的信息。这种方法比起简单的双重循环（时间复杂度为 O(n^2)）要高效得多。

hot-100