牛客hot100--BM50---两数之和(简单难度)

简介: 牛客hot100--BM50---两数之和(简单难度)

目录

题目概述(简单难度)

题目链接:

点我进入牛客

思路与代码

思路展现

这道题目使用哈希是最为简便的

代码示例

import java.util.*;
import java.util.HashMap;
public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        //map用于存储我们整形数组中的数字以及其在数组中对应的下标
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0 ; i < numbers.length ; i++) {
            if(map.containsKey(target - numbers[i])) {
                //注意这里的顺序为什么是这样
                return new int[]{ map.get(target - numbers[i]) + 1 , i + 1};
            }else { 
                map.put(numbers[i] , i);
            }
        }
        return null;
    }
}

时间复杂度:O(n)

一次遍历hashmap查找时间复杂度为O(1),for循环遍历n次,所以时间复杂度为O(N)

空间复杂度:O(n)

申请了n大小的map空间


注意事项

1:牛客中的很多集合都是需要自己导包的,例如这道题题目就需要我们自己导HashMap包

2:那么此时我们的map集合中到底存储的是什么呢?


map中存储的是我们数组中的每个值以及他们的下标

1

3:target - numbers[i]是一个非常巧妙的点,因为我们此时要在这个数组中找到等于target的两个值,并且我们想用一次遍历来完成,所以这样的设计就非常的巧妙了.

4:也是我比较犯迷糊的点,就是为什么这里返回的是new int[]{ map.get(target - numbers[i]) + 1 , i + 1}?

答:我们拿一个测试用例来做举例:

假设此时我们使用【3,2,4】 6这个测试用例来做举例

此时i走到3,发现6 - 3 = 3,map此时为空,根本不存在3这个元素,那么就将3这个元素加入到map当中,然后i走到了2,发现6 - 2 = 4,但是map此时只有3这个元素,并没有4这个元素,所以此时再将2加入到我们的map当中,最终i走到了4这个元素,6 - 4 = 2,发现map中有2这个元素,那么此时就要返回2和4所对应的下标了,因为题目中说了要按照下标升序的顺序返回,我们会发现4是最后才发现的,2是最先发现的,并且让返回的数组下标从1开始计数,所以说我们应该先返回map.get(target - numbers[i]) + 1 ,然后再返回i + 1


相关文章
|
算法
LeetCode 热题 HOT 100题解 (easy级别)(一)
LeetCode 热题 HOT 100题解 (easy级别)
145 0
|
机器学习/深度学习
LeetCode 热题 HOT 100题解 (easy级别)(二)
LeetCode 热题 HOT 100题解 (easy级别)
99 0
每日一题---1005. K 次取反后最大化的数组和[力扣][Go]
每日一题---1005. K 次取反后最大化的数组和[力扣][Go]
每日一题---1005. K 次取反后最大化的数组和[力扣][Go]
每日一题---786. 第 K 个最小的素数分数[力扣][Go]
每日一题---786. 第 K 个最小的素数分数[力扣][Go]
每日一题---786. 第 K 个最小的素数分数[力扣][Go]
每日一题---1380. 矩阵中的幸运数[力扣][Go]
每日一题---1380. 矩阵中的幸运数[力扣][Go]
每日一题---1380. 矩阵中的幸运数[力扣][Go]
每日一题---689. 三个无重叠子数组的最大和[力扣][Go]
每日一题---689. 三个无重叠子数组的最大和[力扣][Go]
每日一题---689. 三个无重叠子数组的最大和[力扣][Go]
|
Go Perl
每日一题---6. Z 字形变换[力扣][Go]
每日一题---6. Z 字形变换[力扣][Go]
每日一题---6. Z 字形变换[力扣][Go]
每日一题 ---- 553. 最优除法[力扣][Go]
每日一题 ---- 553. 最优除法[力扣][Go]
每日一题 ---- 553. 最优除法[力扣][Go]
每日一题 --- 942. 增减字符串匹配[力扣][Go]
每日一题 --- 942. 增减字符串匹配[力扣][Go]
每日一题 --- 942. 增减字符串匹配[力扣][Go]
每日一题---16. 最接近的三数之和[力扣][Go]
每日一题---16. 最接近的三数之和[力扣][Go]
每日一题---16. 最接近的三数之和[力扣][Go]