普歌-允异团队-【算法思路】从入题至解题的详细思路讲解——LeetCode——两数之和

avatar
avatar
云惠网小编
2845
文章
1
评论
2021年4月6日21:19:41 评论 8 次浏览 2045字阅读6分49秒
摘要

【Java知识点】面试中会问到的那些小知识(1)前言题目思路为什么要用哈希表呢?解题前言算法思路是程序员必备的一项能力,某认为刷算法题不仅仅在于给出答案,更在于理解做题的思路流程本文将从入题至解题,进行详细的思路描述,希望能够对你有所帮助

前言

  • 需要注意的是,在做本题之前需要对HashMap所包含的方法有一定的了解,以下是本题中用到的三个HashMap中的方法

题目

至此文章就结束啦,欢迎在评论区留言

  • 在拿到这道题的初期,可以看到最终输出的是数组下标,那么我们可以定义一个数组来接收要输出的数组下标,在主函数中以增强for循环的方式遍历接收数组,输出答案
  • 本题在解题的过程中明确要求,依照一个已知的数,在容器中寻找另一个对应的值是否存在,那么这便是一个典型的K-V键值对的模型,所以我们可以考虑利用HashMap来解题
  • 当然,我们可以采用双层for循环进行暴力求解,在此某不对这种方法做过多阐述
public class TwoSum1 {
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int[] result = twoSum(nums, 9);
for (int i : result) {
System.out.println(i);
}
}
public static int[] twoSum(int[] nums, int target) {
if (nums != null) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int temp = target - nums[i];
if (hashMap.containsKey(temp))
return new int[]{hashMap.get(temp), i};
else
hashMap.put(nums[i], i);
}
}
return null;
}
//以下为用for循环的暴力解法
/*public static int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[0];
}
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - x) {
return new int[]{i, j};
}
}
}
return new int[0];
}*/
}
  • 为什么要用哈希表呢?

以下是本篇文章正文内容,内容仅为某个人见解。欢迎交流


运行结果
在这里插入图片描述

返回值类型 方法 描述
boolean containsKey(Object key) 如果此映射包含指定键的映射,则返回 true
void get(Object key) 返回到指定键所映射的值,或 null如果此映射包含该键的映射
void put(K key, V value) 将指定的值与此映射中的指定键相关联

解题

【算法思路】从入题至解题的详细思路讲解——LeetCode(1)——两数之和

  • 前言
    • 题目
    • 思路
    • 解题
  • 在确定使用HashMap之后,一起来看下一步操作
  • 我们已经建立了一个空的哈希表,如何把数组中的数据转入集合中呢?可以这样操作
  • 首先我们利用for循环遍历数组,同时将目标值在HashMap中查找
    • 如果不存在该数据,则将该数与对应的数组下标以键值对的形式存入集合中
    • 如果存在则返回该数对应的键值,这里的键值就是上一步存入的数组下标
  • 至此本题大致的解题思路便已经明了了
  • 本题在运行时需要遍历源数组,在遍历的同时,记录一些信息,以省去一层循环,相对于双层for循环的暴力解法,这是一种“以空间换时间”的方法
  • 需要记录已经遍历过的数值和它所对应的下标,可以借助查找表来实现,查找表有两个常用的实现 :
    • 哈希表:如果经常需要根据键值对存取值,而且不要求顺序,那么HashMap就是理想的选择
    • 平衡二叉树

算法思路是程序员必备的一项能力,某认为刷算法题不仅仅在于给出答案,更在于理解做题的思路流程
本文将从入题至解题,进行详细的思路描述,希望能够对你有所帮助

同时也推荐看看这些文章
普歌-允异团队-【Java知识点】这些Java学习路上你必须知道的底层原理(2)为什么接口中没有构造方法而抽象类中有构造方法?

(原题)两数之和

在了解这三个方法后相信你已经有了一些想法,那么话不多说直接上代码吧!

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

示例 1:

输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] ==
9 ,返回 [0, 1] 。


同时也祝看完本篇的你在未来的时间里收获更多知识!


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

思路

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


  • 作者:CEMER216
  • 本文版权归作者和CSDN共有,欢迎转载,且在文章页面明显位置给出原文链接,未经作者同意必须保留此段声明,否则保留追究法律责任的权利。

本文转自 https://blog.csdn.net/weixin_51978362/article/details/115433671

腾讯云618
avatar
2w 字长文爆肝 JVM 经典面试题!太顶了! java

2w 字长文爆肝 JVM 经典面试题!太顶了!

如果你是中高级程序员,那我相信你一定被面试官问过JVM。下次再被问到JVM,你直接把老周的这篇文章丢给他吧!话不多说,让我们直接进入主题吧。JVM内存结构,常见异常,调优参数,调优...
JAVA初窥-DAY08 java

JAVA初窥-DAY08

JAVA初窥-DAY08面向过程与面向对象实例化及调用方法和成员变量面向过程与面向对象面向过程:注重的是某件事情过程中的每一个步骤的实现。面向对象:把面向过程中的每一个步骤交给一个...
腾讯云618
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: