两数之和

发表于 更新于 分类于

算法-两数之和

背景

  • 算法–两数之和

  • 博主以代码随想录算法公开课进行学习

题目

  • 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

    你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

    示例:

    给定 nums = [2, 7, 11, 15], target = 9

    因为 nums[0] + nums[1] = 2 + 7 = 9

    所以返回 [0, 1]

思路

  • 使用哈希法的时候：当我们需要查询一个元素是否在集合里的时候
  • 本题需要一个集合来存放我们遍历后的元素，在遍历数组的时候再询问这个集合，看元素是否遍历过
  • map是一种key value的存储结构，key = 数值，value = 下标

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] twoSum(int[] nums, int target) {
         int[] r = new int[2];//储存两个下标
         if(nums == null || nums.length == 0){
            return r;
         }
         Map<Integer,Integer> map = new HashMap<>();
            for(int i=0;i<nums.length;i++){
                int t = target - nums[i]; //通过相减得出另一个数是什么
                if(map.containsKey(t)){ // 关键判断：HashMap中是否存在补数t（说明之前遍历过这个数）
                    r[1] = i;
                    r[0] = map.get(t);
                    break;
                }
                map.put(nums[i],i);  // 若补数不存在，把当前元素的“数值-下标”存入HashMap，供后续元素查询

            }

         return r;
    }
}

总结

  • 为什么会想到用哈希表
    • 当我们需要查询一个元素是否在集合里的时候
  • 哈希表为什么用map
    • Set 只能存 “值”，只能判断补数是否存在；而我们需要同时获取补数的下标，Map 的 “键值对” 结构刚好能满足 “存数值 + 存下标” 的需求。
  • 本题map是用来存什么的
    • 存已遍历过的数组元素及其下标，相当于 “遍历账本”，供后续元素快速查补数
  • map中的key和value用来存什么的
    • key：数值
    • value：数组下标