【动画】从两数之和中，我们可以学到什么？（Python/Java/C++/C/Go/JS/Rust）

方法时间复杂度空间复杂度暴力法O(n²)O(1)哈希表法O(n)O(n)“两数之和”问题虽然简单，却涵盖了算法设计中非常重要的概念：如何在有限的时间内高效地查找满足特定条件的元素对。通过暴力法和哈希表法的对比，我们不仅学习了不同的解题策略，还理解了时间与空间复杂度之间的权衡。在实际编程中，选择合适的数据结构和算法是提高程序性能的关键。哈希表法通过“空间换时间”的策略，显著优化了算法的运行效率，是一

qq_17405059

126人浏览 · 2025-01-11 13:08:13

qq_17405059 · 2025-01-11 13:08:13 发布

【动画】从两数之和中，我们可以学到什么？（Python/Java/C++/C/Go/JS/Rust）

引言

“两数之和”（Two Sum）是算法学习中的经典问题之一，不仅因为其简单明了的题目描述，还因为它涵盖了许多基础的数据结构和算法概念。通过深入理解“两数之和”，我们可以学到如何优化算法、选择合适的数据结构以及理解时间与空间复杂度之间的权衡。本篇博客将详细解析“两数之和”问题，比较不同编程语言（Python、Java、C++、C、Go、JavaScript、Rust）中的解决方案，并探讨背后的算法思想。

问题描述

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

你可以假设每种输入只会对应一个答案，并且你 不能使用相同的元素 两次。

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

提示

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
只会存在一个有效答案

解题思路

“两数之和”问题主要考察的是如何在数组中高效地查找满足特定条件的元素对。我们可以从以下两个常见的解决方案入手：

暴力法（Brute Force）
哈希表法（Hash Table）

1. 暴力法

思路：

暴力法通过枚举数组中所有可能的两数组合，检查它们的和是否等于目标值 target。具体来说，使用两层嵌套循环，第一层遍历数组中的每一个元素，第二层遍历当前元素右边的所有元素，检查是否存在两个数的和等于 target。

代码实现：

# Python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, x in enumerate(nums):
            for j in range(i + 1, len(nums)):
                if x + nums[j] == target:
                    return [i, j]

// Java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i] + nums[j] == target){
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{};
    }
}

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

复杂度分析：

时间复杂度： O(n²)，其中 n 是数组的长度。需要遍历所有可能的两数组合。
空间复杂度： O(1)，仅使用了常数级别的额外空间。

优缺点：

优点： 实现简单，易于理解。
缺点： 对于大规模数据，性能较差，时间复杂度较高。

2. 哈希表法

思路：

哈希表法通过使用一个哈希表（在Python中为字典）来存储数组中元素的值及其对应的下标。在遍历数组的同时，检查当前元素的补数（target - nums[j]）是否已经存在于哈希表中。如果存在，则找到了满足条件的两个数；否则，将当前元素及其下标存入哈希表中。

代码实现：

# Python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        idx = {}
        for j, x in enumerate(nums):
            if target - x in idx:
                return [idx[target - x], j]
            idx[x] = j

// Java
import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> idx = new HashMap<>();
        for(int j=0; j<nums.length; j++){
            if(idx.containsKey(target - nums[j])){
                return new int[]{idx.get(target - nums[j]), j};
            }
            idx.put(nums[j], j);
        }
        return new int[]{};
    }
}

// C++
#include <unordered_map>
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> idx;
        for(int j=0; j<nums.size(); j++){
            if(idx.find(target - nums[j]) != idx.end()){
                return {idx[target - nums[j]], j};
            }
            idx[nums[j]] = j;
        }
        return {};
    }
};

复杂度分析：

时间复杂度： O(n)，其中 n 是数组的长度。只需遍历一次数组，每次查找和插入哈希表的时间复杂度均为O(1)。
空间复杂度： O(n)，用于存储哈希表中的元素。

优缺点：

优点： 大幅减少了时间复杂度，适用于大规模数据。
缺点： 需要额外的空间来存储哈希表。

为什么哈希表法比暴力法更快？

在暴力法中，每次仅比较两个数，获取的信息量为 O(1)。而在哈希表法中，通过哈希表的辅助，我们在每一步可以查找到是否存在满足条件的数，这实际上在每一步获取了 O(n) 的信息。因此，尽管每次操作的时间复杂度都是 O(1)，但由于信息量的提升，使得整体算法的时间复杂度从 O(n²) 优化到了 O(n)。

多语言实现

为了更好地理解不同编程语言中如何实现哈希表法，以下提供了多种语言的代码示例。

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        idx = {}
        for j, x in enumerate(nums):
            if target - x in idx:
                return [idx[target - x], j]
            idx[x] = j

Java

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> idx = new HashMap<>();
        for(int j=0; j<nums.length; j++){
            if(idx.containsKey(target - nums[j])){
                return new int[]{idx.get(target - nums[j]), j};
            }
            idx.put(nums[j], j);
        }
        return new int[]{};
    }
}

C++

#include <unordered_map>
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> idx;
        for(int j=0; j<nums.size(); j++){
            if(idx.find(target - nums[j]) != idx.end()){
                return {idx[target - nums[j]], j};
            }
            idx[nums[j]] = j;
        }
        return {};
    }
};

C

#include <stdlib.h>

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int* returnArray = (int*)malloc(2 * sizeof(int));
    for(int i=0;i<numsSize;i++){
        for(int j=i+1;j<numsSize;j++){
            if(nums[i] + nums[j] == target){
                returnArray[0] = i;
                returnArray[1] = j;
                *returnSize = 2;
                return returnArray;
            }
        }
    }
    *returnSize = 0;
    return returnArray;
}

注：C语言的实现通常采用暴力法，因为标准C库不提供哈希表支持，若需使用哈希表，需要自行实现或使用第三方库。

Go

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

JavaScript

var twoSum = function(nums, target) {
    const idx = {};
    for(let j = 0; j < nums.length; j++){
        const complement = target - nums[j];
        if(complement in idx){
            return [idx[complement], j];
        }
        idx[nums[j]] = j;
    }
};

Rust

use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut idx = HashMap::new();
        for (j, &x) in nums.iter().enumerate() {
            if let Some(&i) = idx.get(&(target - x)) {
                return vec![i as i32, j as i32];
            }
            idx.insert(x, j);
        }
        vec![]
    }
}