LeetCode两数之和

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

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

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

解题思路

为了高效地解决这个问题，我们可以使用 哈希表（HashMap） 来存储数组中的元素及其对应的索引。这样可以在一次遍历中完成查找，时间复杂度为 O(n)。

具体步骤如下：

1. 初始化一个空的哈希表，用于存储数组元素的值和对应的索引。
2. 遍历数组：
   • 对于当前元素 nums[i]，计算需要的补数 complement = target - nums[i]。
   • 检查补数是否存在于哈希表中：
     • 如果存在，说明找到了两个数的和等于目标值，返回它们的索引。
     • 如果不存在，将当前元素及其索引存入哈希表中，继续遍历。
3. 如果遍历结束后仍未找到符合条件的两个数，抛出异常或返回特殊值（根据具体需求）。

这种方法的优势在于，只需遍历一次数组即可找到结果，且查找和插入哈希表的时间复杂度都是 O(1)。

Java代码实现

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

public class TwoSum {
    
    /**
     * 找出数组中两个数之和等于目标值的索引。
     *
     * @param nums   整数数组
     * @param target 目标和
     * @return 两个数的索引数组
     * @throws IllegalArgumentException 如果没有找到符合条件的两个数
     */
    public static 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");
    }
    
    // 示例用法
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        
        try {
            int[] result = twoSum(nums, target);
            System.out.println("索引为: " + result[0] + " 和 " + result[1]);
            // 输出: 索引为: 0 和 1
        } catch (IllegalArgumentException e) {
            System.out.println(e.getMessage());
        }
    }
}

代码详解

1. 哈希表的使用：

   • 我们使用 HashMap<Integer, Integer> 来存储数组中的数值和它们对应的索引。键（Key）为数组中的数值，值（Value）为数值对应的索引。

2. 遍历数组：

   • 对于每个元素 nums[i]，我们计算它的补数 complement = target - nums[i]。
   • 使用 numToIndex.containsKey(complement) 来检查补数是否已经在哈希表中。如果存在，说明之前已经遍历过一个数，它与当前数的和等于目标值，我们可以直接返回这两个数的索引。
   • 如果补数不存在，我们将当前数和它的索引存入哈希表，以便后续的元素可以使用它。

3. 异常处理：

   • 根据题目要求，每个输入只会有一个解，因此如果遍历完数组后仍未找到符合条件的两个数，我们抛出一个 IllegalArgumentException 异常。

4. 示例：

   • 在 main 方法中，我们以数组 {2, 7, 11, 15} 和目标值 9 为例。
   • 运行结果为索引 0 和 1，因为 nums[0] + nums[1] = 2 + 7 = 9。

时间和空间复杂度

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次，每次查找和插入哈希表的时间都是常数时间。
• 空间复杂度：O(n)，因为在最坏情况下，我们需要存储数组中所有的元素到哈希表中。

总结

通过使用哈希表，我们能够高效地解决“两数之和”问题。这个方法不仅简单易懂，而且在实际编程中应用广泛，是解决类似问题的一种常见技巧。