力扣Java - 1. 两数之和
两数之和
- 题目描述
- 题目分析
- 示例演示
-
-
-
- 示例一
- 示例二
- 示例三
-
-
- 算法思想
- 算法代码
- 代码解释
题目描述
- 一个整数数组 nums 和一个整数目标值 target。
- 在该数组中找出和为目标值 target 的那两个整数,并返回它们的数组下标。
- 假设每种输入只会对应一个答案。
- 数组中同一个元素在答案里不能重复出现。
- 你可以按任意顺序返回答案。
题目分析
题目描述太多了,不想看?一句话概况问题。
nums[i] + nums[j] = target ,i ≠ j
示例演示
示例一
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例二
输入:nums = [3,2,4], target = 6
输出:[1,2]
示例三
输入:nums = [3,3], target = 6
输出:[0,1]
算法思想
- 使用map集合解决问题,因为map集合中的元素是 “key - value” 的形式,使用key存储数组元素值,value存储数组下标。
- 为什么使用key存储元素值,而不是用value存储?这是因为map集合提供了get(Object key)方法,可以根据key值返回value值。结合本题就是可以根据数组元素值来获得数组下标,因为题目要求返回数组下标。
- map集合也提供了containsKey(Object key)方法,用于判断当前map集合中是否存在指定key。可以使用该方法判断集合中是否存在值为 “target - nums[i]” 的key,如果存在,则成功解决问题。
算法代码
class Solution { public int[] twoSum(int[] nums, int target) { HashMap<Integer,Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++){ if(map.containsKey(target - nums[i])){ return new int[]{map.get(target - nums[i]),i}; } map.put(nums[i],i); } throw new RuntimeException("找不到符合要求的答案!"); }}
代码解释
- 依次遍历数组元素。
- 在遍历过程中如果发现map中存在值为 “target - nums[i]” 的key,使用map集合提供的get方法获取到该key所对应的value值,将 i 和 value 值打包成一个int型数组返回。
- 如果不满足 if 条件,则将该数组元素存入map集合中,继续遍历数组元素,一边遍历一遍判断是否存在所需key。
- 如果 for 循环执行完还是没有执行 return 语句,则手动抛出一个异常。