面试高频算法题---两数之和

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

🍔题目

题目链接:两数之和


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


每种输入只会对应一个答案,但是数组中同一个元素在答案里不能同时出现,可以按照任意顺序返回答案。


示例:

微信图片_20221029152811.png

🌭题目解析

image.png

🍟解题思路及代码展示

🥫思路1

暴力解决,题目要求两数之和,所以每个数对应一个循环,也就是两个循环嵌套,当满足这两个数的和等于目标值时,保存这两个数的下标然后返回


image.png

👁️‍🗨️代码展示:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ret = new int[2];
        for(int i = 0;i < nums.length;i++){
            for(int j = i+1;j < nums.length;j++){
                if(nums[i]+nums[j] == target){
                    ret[0] = i;
                    ret[1] = j;
                    return ret; //找到值后直接返回,避免后续循环
                }               
            }
        }
        return ret;
    }
}


时间复杂度:两层循环嵌套,故时间复杂度为O(n^2)


🥫思路2

我们可以借助HashMap这一数据结构,遍历数组,判断HashMap中的key是否存有target-nums[i],如果存在,第一个数的下标为hashmap.get(target-nums[i]),第二个数的下标为i,如果不存在,将nums[i]-i作为K-V键值对存入HashMap中,依次循环直到判断存在


🤔解释说明:

image.png



👁️‍🗨️代码展示:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> m = new HashMap<>();
        int[] ret = new int[2];
        for(int i = 0;i < nums.length;i++){
            if(m.containsKey(target-nums[i])){
                ret[0] = m.get(target-nums[i]);
                ret[1] = i;
            }
            m.put(nums[i],i); //存入值-下标
        }
        return ret;
    }
}


时间复杂度:只有一个循环,故时间复杂度为O(n)  


相关文章
|
3月前
|
负载均衡 NoSQL 算法
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
这篇文章是关于Java面试中Redis相关问题的笔记,包括Redis事务实现、集群方案、主从复制原理、CAP和BASE理论以及负载均衡算法和类型。
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
|
3月前
|
算法 Go
[go 面试] 雪花算法与分布式ID生成
[go 面试] 雪花算法与分布式ID生成
|
14天前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
20天前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
28 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
8天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
14天前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
22天前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
50 2
|
2月前
|
机器学习/深度学习 JavaScript 算法
面试中的网红虚拟DOM,你知多少呢?深入解读diff算法
该文章深入探讨了虚拟DOM的概念及其diff算法,解释了虚拟DOM如何最小化实际DOM的更新,以此提升web应用的性能,并详细分析了diff算法的实现机制。
|
3月前
|
JavaScript 算法 索引
【Vue面试题二十三】、你了解vue的diff算法吗?说说看
这篇文章深入分析了Vue中的diff算法,解释了其在新旧虚拟DOM节点比较中的工作机制,包括同层节点比较、循环向中间收拢的策略,并通过实例演示了diff算法的执行过程,同时提供了源码层面的解析,说明了当数据变化时,如何通过Watcher触发patch函数来更新DOM。
【Vue面试题二十三】、你了解vue的diff算法吗?说说看
|
3月前
|
算法
聊聊一个面试中经常出现的算法题:组合运算及其实际应用例子
聊聊一个面试中经常出现的算法题:组合运算及其实际应用例子