力扣刷题 | 两数之和

目录

1. 引言
2. 问题描述
3. 示例与案例分析
   • 案例一：基本用法
   • 案例二：边界情况
   • 案例三：大数据集
4. 思路解析
   • 暴力解法
   • 哈希表解法
5. 代码实现
   • Python 实现
   • Java 实现
6. 复杂度分析
7. 扩展问题
   • 扩展问题一：三数之和
   • 扩展问题二：四数之和
8. 总结

引言

在算法练习中，“两数之和”是一个经典的问题，常常出现在面试和编程竞赛中。掌握这个问题的解决方案不仅有助于提高编程能力，还能锻炼思维方式。在本篇文章中，我们将详细探讨这个问题，包括问题描述、解决方案、代码实现以及复杂度分析。

问题描述

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

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

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

函数签名

pythonCopy Code
def two_sum(nums: List[int], target: int) -> List[int]:

示例与案例分析

案例一：基本用法

输入：

plaintextCopy Code
nums = [2, 7, 11, 15]
target = 9

输出：

plaintextCopy Code
[0, 1]

解释：

因为 nums[0] + nums[1] == 9，返回 [0, 1]。

案例二：边界情况

输入：

plaintextCopy Code
nums = [3, 2, 4]
target = 6

输出：

plaintextCopy Code
[1, 2]

解释：

nums[1] + nums[2] == 6，返回 [1, 2]。

案例三：大数据集

输入：

plaintextCopy Code
nums = [1] * 10**6 + [2]
target = 3

输出：

plaintextCopy Code
[999998, 999999]

解释：

在大数据集中，找到两个数字的和为目标值的情形。

思路解析

暴力解法

暴力解法的思路非常简单，使用两层循环遍历数组中的每一对数字，检查它们的和是否等于目标值。

实现步骤：

1. 遍历数组 nums。
2. 对于每个数字，使用另一个循环去查找能够与之相加得到 target 的数字。
3. 一旦找到满足条件的两数，就返回它们的索引。

时间复杂度

这个方法的时间复杂度为 O(n²)，其中 n 是数组的长度。由于需要双重循环，因此效率较低。

哈希表解法

哈希表解法使用额外的空间来存储数组元素及其索引，以便快速查找。具体步骤如下：

1. 初始化一个空的哈希表。
2. 遍历数组 nums：
   • 计算当前数字 num 与目标值 target 的差值 complement。
   • 如果 complement 已经存在于哈希表中，说明找到了满足条件的两个数，返回它们的索引。
   • 否则，将当前数字和它的索引存入哈希表中。

时间复杂度

这种方法的时间复杂度为 O(n)，因为只需遍历一次数组。

代码实现

Python 实现

pythonCopy Code
def two_sum(nums, target):
    num_to_index = {}
    for index, num in enumerate(nums):
        complement = target - num
        if complement in num_to_index:
            return [num_to_index[complement], index]
        num_to_index[num] = index
    return []

Java 实现

javaCopy Code
import java.util.HashMap;
import java.util.Map;

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

复杂度分析

• 时间复杂度：O(n)，因为我们只遍历了一次数组。
• 空间复杂度：O(n)，最坏情况下哈希表需要存储 n 个元素。

扩展问题

扩展问题一：三数之和

在三数之和的问题中，要求在数组中找到三个数，使它们的和为零。解决这个问题可以借鉴两数之和的思路，但需要进行更多的组合和排序。

扩展问题二：四数之和

类似于三数之和，这个问题要求找到四个数使得它们的和为目标值。解决方案通常涉及到嵌套的循环或多指针技术。

总结

“两数之和”是一个非常重要的算法问题，常常作为基础问题出现在各种场合。通过本文的详细讲解，相信读者对这道题有了更深入的理解和掌握。不论是在面试中，还是在实际工作中，掌握这些基础算法都是非常有益的。

希望这篇文章能帮助你在力扣上更好地进行刷题训练！