LeetCode第一题详解：两数之和的暴力解法与哈希表优化

LeetCode第一题详解：两数之和的暴力解法与哈希表优化

引用

CSDN

1.

https://blog.csdn.net/2301_78566776/article/details/143580630

本文将为大家介绍LeetCode第一题“两数之和”的两种解法：暴力解法和哈希表解法。通过对比两种方法的时间复杂度和空间复杂度，帮助读者理解如何在实际编程中选择最优解。

题目描述

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

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

示例：

方法一：暴力解法

暴力解法是最直观的解法，通过两个嵌套循环遍历数组中的每一个数，查看是否有与之对应的数使得二者之和为 target。

值得注意的是：每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找即可。（所以下面代码第二层循环的开始是 j=i+1）

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[] {};
    }
}

• 时间复杂度：O(N^2)，其中 N 是数组中的元素数量。
• 空间复杂度：O(1)。

方法二：哈希表解法

哈希表法体现了“空间换时间”的思想。在遍历的同时，记录一些信息，以省去一层循环。具体来说，需要记录已经遍历过的数值和它对应的下标，可以借助查找表实现。

查找表通常有：哈希表、平衡二叉搜索树。我们不需要维护所存数组的顺序性，使用哈希表即可。

图解说明

1. 首先我们把第一个元素存入哈希表中，位置为0
2. 此后将后续元素存入哈希表，存入前需要检查哈希表里有没有和它配对的元素，有的话返回这两个元素的下标，没有的话，将该元素存入哈希表。
3. 哈希表的长度为len-1即可。

代码实现

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len=nums.length;
        //初始化哈希表，要求规定其大小
        Map<Integer,Integer>hashMap=new HashMap(len-1);
        //存入第一个元素
        hashMap.put(nums[0],0);
        //其余元素循环遍历
        for(int i=1;i<len;i++){
            //定义另一个要在哈希表中寻找的元素
            int another =target-nums[i];
            //判断哈希表中是否存在
            if(hashMap.containsKey(another)){
                //如果存在，返回二者下标
                return new int[]{i,hashMap.get(another)};
            }else{
                //不存在将该元素存入哈希表
                hashMap.put(nums[i],i);
            }
        }
        //任意返回
        return new int[] {0};
    }
}

注意：根据题目规定，代码是不会执行到 return new int[] {0}; 这一行的。所以我们可以返回任意值。当然我们也可以抛回一个异常：

throw new IllegalArgumentException("No two sum solution");

通过对比两种解法，我们可以看到哈希表解法在时间复杂度上有明显的优势，虽然牺牲了一定的空间复杂度，但在实际应用中通常是一个值得的选择。