【数组】两数之和

小鱼儿 2022-11-26 07:56 188阅读 0赞

### [【2020秋招-面试题目汇总（随时更新）】][2020_-] ###

# 1. 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]

# 2. 题目分析 #

1.  我们首先想到的，是暴力，直接双重循环，这种的耗费时间为O（n^2），也不是面试官想要看到的，我们需要在此方法的基础上对其改进。
2.  我们想到了一种数据结构（HashMap），我们知道，对于HashMap而言，它具有（key-value）的一种映射，我们将 **target - nums\[i\]** 设置为**key**，将它的下标**i**设置为**value**,这样的话， 当我们在数组中再一次遍历到\*\*target - nums\[i\]\*\*时，将 **value** 和当前的下标设置返回

if (map.containsKey(nums[i])) {
        
    				res[0] = map.get(nums[i]);
                    res[1] = i;
    			} else {
        
    				map.put(target - nums[i], i);
    			}

# 3. 题目代码 #

class Solution {
        
       public int[] twoSum(int[] nums, int target) {
        
    		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    		int[] res = new int[2];
    		for (int i = 0; i < nums.length; i++) {
        
    			if (map.containsKey(nums[i])) {
        
    				res[0] = map.get(nums[i]);
                    res[1] = i;
    			} else {
        
    				map.put(target - nums[i], i);
    			}
    		}
    		return res;
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]

[2020_-]: https://blog.csdn.net/qq_40915439/article/details/107908926
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: /images/20221124/17edac25b25045bda199828068a5ce7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]: /images/20221124/cf44899a0ee64394b5ee59afe5b8f22c.png