一篇文章彻底掌握「两数之和」：Go/Java/Python 最优解法详解

问题描述

「两数之和」是LeetCode上最经典的算法题之一，题目要求：

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

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

示例：

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

解法思路分析

1. 暴力解法（不推荐）

最直观的方法是双重循环遍历所有可能的组合：

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

2. 哈希表优化解法（最优解）

利用哈希表存储已经遍历过的数字及其索引，可以将时间复杂度降为O(n)：

各语言最优实现

Go 实现

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

特点：

• 使用map[int]int存储值到索引的映射
• if k, ok := m[target-v]; ok 是Go特有的map访问方式
• 清晰简洁，性能优秀

Java 实现

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

特点：

• 使用HashMap存储数据
• 需要处理无解情况（抛出异常）
• 类型系统更严格

Python3 实现

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

特点：

• 使用字典存储数据
• enumerate获取索引和值
• 代码最为简洁

算法分析

时间复杂度

三种实现的时间复杂度都是O(n)，因为：

• 只需要遍历数组一次
• 哈希表的查找操作是O(1)时间复杂度

空间复杂度

空间复杂度都是O(n)，因为：

• 最坏情况下需要存储所有元素到哈希表

边界情况测试

实际应用场景

1. 支付系统：查找两笔交易金额之和等于特定值
2. 游戏开发：查找两个物品的组合效果
3. 数据分析：找出满足特定条件的两个数据点

总结

「两数之和」问题虽然简单，但包含了算法设计的核心思想：

1. 从暴力解法入手理解问题
2. 通过空间换时间优化性能
3. 考虑各种边界情况
4. 掌握不同语言的实现特点

三种语言的实现虽然语法不同，但核心算法思想完全一致。建议读者：

1. 先理解算法思路
2. 然后学习自己主要使用语言的实现
3. 最后尝试用其他语言实现以加深理解

扩展思考

1. 如果数组已排序，是否有更优解法？（可以使用双指针法，空间复杂度O(1)）
2. 如果要求返回所有可能的解而不仅是一个，如何修改代码？
3. 如果数组非常大，如何优化内存使用？

希望这篇文章能帮助你彻底掌握「两数之和」问题！如果有任何疑问，欢迎在评论区留言讨论。