牛客网面试必刷：BM50 两数之和

灰太狼 2024-03-22 17:33 21阅读 0赞

#### 牛客网面试必刷：BM50 两数之和 ####

*  前言
 *  一、解法1：Hash表

--------------------

## 前言 ##

**给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。  
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）**  
![在这里插入图片描述][ecf0c83337ba4160885683f5ee581a2b.png]

--------------------

## 一、解法1：Hash表 ##

**哈希表的思想为「以空间换时间」，这是由于哈希表保存了键值对，其「查找」复杂度为O(1)。**

对于本题，具体解题思路为（如图所示）：

step 1：定义哈希表hashmap，其存放的键值对为<取值，下标>。

step 2：从开始处遍历数组，对于第i个位置，在哈希表中寻找target-nums\[i\]是否存在，若存在，将两个下标放入数组中返回；若不存在，将其添加至表中，继续遍历

import java.util.*;
    
    
    public class Solution {
        
        /**
         * 
         * @param numbers int整型一维数组 
         * @param target int整型 
         * @return int整型一维数组
         */
        public int[] twoSum (int[] numbers, int target) {
        
            // write code here
            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 new int[]{
        0,0};
        }
    }

![在这里插入图片描述][312936e6e43d408abbf971ad28b8725e.png]

![在这里插入图片描述][6c310ab4260b4c49b4646cf9dd46ce99.png]

[ecf0c83337ba4160885683f5ee581a2b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/c87460a3321c4503bf99419d14e73be3.png
[312936e6e43d408abbf971ad28b8725e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/264cfacc9a814796a2541663f94ea84a.png
[6c310ab4260b4c49b4646cf9dd46ce99.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/59aa44b8e92545fd827442a6ec306a73.png