001两数之和

2023-12-13 04:18:17

题意

给出一个数组和一个目标值,让你在数组中找出和为目标值的两个数,并且这两个数在数组中的下标(索引)不同。

示例

输入:nums=[2,7,11,15],target=9

输出:[0,1]

解释:因为nums[0]+nums[1]==9,返回[0,1]

分析

所谓的“暴力”,在算法领域表示“穷举、极低效率的实现”。主要源于这个英文单词(Brute-Force,暴力攻击)。

两层遍历,第一层确定第一个数,第二层确定第二个数,用一个加法运算就可以完成题目的要求。

classSolution{
//定义一个方法twoSum,接收一个整数数组nums和一个目标值target
publicint[]twoSum(int[]nums,inttarget){
//外层循环遍历数组中的每个元素
for(inti=0;i<nums.length;i++){
//内层循环从当前元素的下一个开始遍历
for(intj=i+1;j<nums.length;j++){
//检查当前选中的两个数之和是否等于目标值
if(nums[i]+nums[j]==target)
//如果等于目标值,返回这两个数的索引
returnnewint[]{i,j};
}
}

//如果遍历完数组都没有找到符合条件的两个数,则抛出异常
thrownewIllegalArgumentException("没有找到");
}
}

笔试如果遇到不太会的题,就暴力。不过两次遍历的时间复杂度是 。

时间复杂度,在算法领域是一个非常重要的概念,一个衡量算法执行时间随输入数据规模增长而增长的度量。在这个特定的 “两数之和” 问题的解法中,时间复杂度是由两层嵌套循环决定。

时间复杂度实在是太不理想,效率太低,在所有 Java 提交中只能击败不到 28% 的用户。

虽然击败了 33% 的 Java 选手,但是这样的算法时间复杂度和之前相比根本没有变化。

我们反推一下。

已知 i 和 target,那么target - i就是与 i 相配对的另一个数,我们只需要判断target - i是否在 i 之前出现过,如果出现过,那么这两个数就是我们要找的数。

那么问题来了,如何判断target - i是否在 i 之前出现过呢?

我们可以用一个 HashMap 来记录数组中的每一个元素,元素的索引作为哈希表的 key,元素本身作为 value,当发现target - i在哈希表中存在时,就可以直接返回这两个数的索引了。来看题解。

class Solution {
    //定义一个方法twoSum,接收一个整数数组nums和一个目标值target
    public int[] twoSum(int[] nums, int target) {
        //定义一个HashMap用于存储数组元素以及他的索引

        HashMap<Integer,Integer> map = new HashMap<>();
        //遍历数组中的每一个元素
        for(int i = 0 ;i<nums.length;i++){
            //计算与当前元素配对的元素
            int complement = target - nums[i];
            //检查HashMap中是否已经存在配对元素
           if(map.containsKey(complement)){
               //存在,就将两元素的下标进行返回
               return new int[]{i , map.get(complement)};
           }
           //将当前元素及其索引添加到哈希表中
           map.put(nums[i] ,i);

        }
       
throw new IllegalArgumentException("没找到");

    }
}

当输入是 nums = [2,7,11,15] 和 target = 9 时,我们来模拟上述解决 “两数之和” 的整个过程:

  1. 初始化哈希表:开始时,哈希表为空。
  2. 遍历数组
  3. 第一个元素(i = 0):nums[0] = 2
  4. 计算 complement = target - nums[i] = 9 - 2 = 7。
  5. 检查哈希表中是否存在 7。目前哈希表为空,所以不存在。
  6. 将 (2, 0) 加入哈希表(值为 2,索引为 0)。
  7. 第二个元素(i = 1):nums[1] = 7
  8. 计算 complement = 9 - 7 = 2。
  9. 检查哈希表中是否存在 2。是的,它存在,并且索引为 0。
  10. 找到匹配的一对元素:nums[0] = 2 和 nums[1] = 7,它们的和为 9。
  11. 返回这两个元素的索引 [1, 0]。

因此,对于输入 nums = [2,7,11,15] 和 target = 9,该题解会返回 [1, 0] 作为结果,表示 nums 数组中索引为 1 和 0 的元素相加得到目标值 9。

时间复杂度:

空间复杂度:

哦吼,这次结果就不一样了,打败了 71% 的选手,效果显著。

总结

对于本题,我们用到了 Java 中的一个普通 for 循环,和一个 HashMap,这两个都是 Java 中必须掌握的知识,如果你对这两个都不熟悉,那么你的 Java 基础还是不够扎实。

建议通过下面三个链接来学习:

  1. Java for 循环
  2. 数组
  3. HashMap

力扣链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

一步一个脚印

不积跬步无以至千里,不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了

文章来源:https://blog.csdn.net/qq_64948664/article/details/134918445
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。