目录
题目
思路
暴力解法
哈希表
代码
暴力解法
哈希表
题目
给定一个整数数组 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]
思路
暴力解法
直接两个for循环
哈希表
- 为什么会想到用哈希表
- 哈希表为什么用map
- 本题map是用来存什么的
- map中的key和value用来存什么的
依次遍历数组中的元素得到a，然后把遍历过的元素放在map里，包括他的key也存进去，然后查找 在map里有没有一个数字和map相加等于target
即查找是否有某个元素，所以用哈希表
哈希表中有数组，set和map，应该选用哪个呢？
- 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
- set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
所以使用map，那么数字和下标哪个是key，哪个是value呢？
我们找的是某个元素是否出现过，所以应该使用key来存储元素，value存储下标
所以先用target-当前遍历元素得到c，如果 c在map的key里面，那么返回c的value和当前元素的下标，即为最后的结果，如果没有在map存储过c，那么也就说明没有找到，把当前遍历的元素存入map中去，连通他的value即下标。
代码
暴力解法
class Solution {public int[] twoSum(int[] nums, int target) {for(int i=0;i<nums.length;i++){for(int j=i+1;j<nums.length;j++){if(nums[i]+nums[j]==target){return new int[]{i,j};}}}return null;}
}哈希表
class Solution {public int[] twoSum(int[] nums, int target) {int[] res=new int[2];//最后返回的两个数字的下标组成的数组if(nums.length==0||nums==null){return res;}Map<Integer,Integer> map=new HashMap<>();//哈希表for(int i=0;i<nums.length;i++){int temp=target-nums[i];//找到相加为目标值的另一个数字if(map.containsKey(temp)){//如果map里包含这个数字res[0]=i;res[1]=map.get(temp);break;}map.put(nums[i],i);//如果没有包含那么把当前遍历的数字加进来}return res;}
}
)