LeetCode 1-两数之和

题目链接

题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

解题思路

判断：

• 暴力解法：两层 for 循环查找，时间复杂度为 O(n²)
• 哈希法：
  • 本题需要一个集合存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是是否出现在这个集合。因此采用哈希法。
  • 本题，不仅要知道元素是否遍历过，还要知道这个元素对应的下标。因此使用map，key存元素，value存下标。

什么时候使用哈希法？
当我们需要查询一个元素是否出现过，或者一个元素是否在集合里时，就要第一时间想到哈希法。

代码

使用哈希表 Map：2ms，43.8M

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]; // 遍历当前元素，并在map寻找是否有匹配的Key
            if(map.containsKey(temp)){
                res[0] = i;
                res[1] = map.get(temp);
                break;
            }
            map.put(nums[i], i); // 如果没有找到匹配对，将其添加到map中
        }
        return res;
    }
}

也可以使用双指针法，之后再看。

复杂度

• 时间复杂度
  O(n)
• 空间复杂度
  O(n)

难点

• 遍历数组存入map后，如何判断其中的哪两个数之和为 target
  • 这道题中，我们需要给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。map 中的存储结构应为{key: 数据元素, value: 数组元素对应的下标}
  • 在遍历数组时，只需要向 map 查询是否有和目前遍历元素匹配的数值，如果有，就找到匹配对；如果没有，就把目前遍历的元素放进 map 中，因为 map 存放的就是我们访问过的元素。

总结

学习到新知识：哈希表的使用场景

• 数组：大小受限制，而且如果元素很少、哈希值太大，会造成内存空间的浪费
• set：set 是一个集合，里面放的元素只能是一个 key。而这道题目，不仅要判断 y 是否存在，还要记录 y 的下标位置，因为要返回 x 和 y 的下标，所以 set 也不能用。
• map：map是一种key value的存储结构。对于本题，可以用key保存数值，用value再保存数值所在的下标。