LeetCode:1.两数之和——Java 暴力解法&哈希表

目录

题目如下： 

​编辑

方法一：暴力解法

方法二：哈希表解法

---

题目如下： 

1. 两数之和https://leetcode.cn/problems/two-sum/

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

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

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

• 只会存在一个有效答案

方法一：暴力解法

我们很容易想到用两个for循环。遍历数组中的每一个数，查看是否有与之对应的数使得二者之和为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};
                }
            }

• 时间复杂度：O(N2)，其中 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 IllegalArgument Exception("No the sum result");

 

原文地址：https://blog.csdn.net/2301_78566776/article/details/143580630

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！