一、题目描述

原文链接：1. 两数之和

具体描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1：

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

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• 只会存在一个有效答案

二、思路分析

乍眼一看，这不双层for循环就可以解决嘛！一层从i开始，一层从i + 1开始，知道找到两个数为止，返回两个下标就是答案！
通过看提示其实O(n^2)是可以过的！因为nums最长也就是10^4嘛，根据巨人经验一般2万以内是O(n^2)是最大范围，2千万是O(nlogn)的最大范围，5亿是O(n)的最大范围！

但是咱们怎么能止于暴力破解那！
题目需要我们记录下标，我们可以想想数据结构，昨天用Set做的题，但是它不能记录值呀，还有一种结构是Map试试呗！
我们可以遍历数组，依次把数值放到Map中，值为key，下标为value
遍历的同时，求一个目标值减去当前数组值int tmp = target - nums[i]，并判断tmp是否在Map中存在，存在的话说明存在的值就是结果值的第一个下标，而i就是第二个下标！
这不结果就出来啦～

注意做一些必要的判断！

if (nums == null || nums.length <= 0){    return res;}

三、AC代码

暴力破解的方法：

class Solution {    public int[] twoSum(int[] nums, int target) { int[] res = new int[2]; for (int i = 0; i < nums.length - 1; i ++){     int oneNum = nums[i];     for (int j = i + 1; j < nums.length; j++){  if (oneNum + nums[j] == target) {      res[0] = i;res[1] = j;      break;  }     } } return res;    }}

Map数据结构的写法：

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

四、总结

• 当无序且唯一想想Set
• 当需要存储值的时候想想Map

感谢大家的阅读，我是Alson_Code，一个喜欢把简单问题复杂化，把复杂问题简单化的程序猿！ ❤