代码随想录算法训练营第十天|1. 两数之和,第454题.四数相加II

发布于:2024-10-17 ⋅ 阅读:(49) ⋅ 点赞:(0)

文档讲解:代码随想录

难度:一般嗷~~

1. 两数之和

力扣题目链接(opens new window)

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

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

示例:

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

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

所以返回 [0, 1]

视频:《代码随想录》算法视频公开课 (opens new window)梦开始的地方,Leetcode:1.两数之和 (opens new window)

思路 

首先再强调一下 什么时候使用哈希法,当我们需要查询一个元素是否出现过,或者一个元素是否在集合里的时候,就要第一时间想到哈希法。

因为本题,我们不仅要知道元素有没有遍历过,还要知道这个元素对应的下标,需要使用 key value结构来存放,key来存元素,value来存下标,那么使用map正合适

再来看一下使用数组和set来做哈希法的局限。

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

此时就要选择另一种数据结构:map ,map是一种key value的存储结构,可以用key保存数值,用value再保存数值所在的下标。

此时就要选择另一种数据结构:map ,map是一种key value的存储结构,可以用key保存数值,用value再保存数值所在的下标。

C++中map,有三种类型:

映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::map 红黑树 key有序 key不可重复 key不可修改 O(log n) O(log n)
std::multimap 红黑树 key有序 key可重复 key不可修改 O(log n) O(log n)
std::unordered_map 哈希表 key无序 key不可重复 key不可修改 O(1) O(1)

std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。

这道题目中并不需要key有序,选择std::unordered_map 效率更高!

接下来需要明确两点:

  • map用来做什么
  • map中key和value分别表示什么

map目的用来存放我们访问过的元素,因为遍历数组的时候,需要记录我们之前遍历过哪些元素和对应的下标,这样才能找到与当前元素相匹配的(也就是相加等于target)

接下来是map中key和value分别表示什么。

这道题 我们需要 给出一个元素,判断这个元素是否出现过,如果出现过,返回这个元素的下标。

那么判断元素是否出现,这个元素就要作为key,所以数组中的元素作为key,有key对应的就是value,value用来存下标。

所以 map中的存储结构为 {key:数据元素,value:数组元素对应的下标}。

在遍历数组的时候,只需要向map去查询是否有和目前遍历元素匹配的数值,如果有,就找到的匹配对,如果没有,就把目前遍历的元素放进map中,因为map存放的就是我们访问过的元素。

过程如下:

过程一

过程二

补充: 

在Java中,Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>(); 这行代码定义了一个类型为Integer的键和值的Map集合,并初始化为HashMap类型。

这行代码的具体含义如下:

  • Map<Integer, Integer>:定义了一个Map集合,其中键和值的数据类型都是Integer
  • hashtable:是该Map集合的变量名。
  • new HashMap<Integer, Integer>():初始化了一个HashMap对象,并将其赋值给hashtable变量。HashMapMap接口的一个实现类,允许使用null键和null值,并且不保证映射的顺序。

在Java中,Map接口的实现类有多种,如HashMapTreeMapLinkedHashMap等。这些实现类有不同的特性和用途,例如:

  • HashMap:基于哈希表的Map接口实现。它不保证映射的顺序,但允许使用null键和null值。
  • TreeMap:基于红黑树的Map接口实现,能够确保其键值按照排序顺序进行存储。
  • LinkedHashMap:基于哈希表的Map接口实现,维护着一个双向链表记录插入顺序或最近访问顺序(取决于访问顺序模式)。

这些实现类可以根据具体需求选择使用,例如如果需要保持插入顺序,可以使用LinkedHashMap;如果需要排序的Map,可以使用TreeMap

图片来自:Map<String,Integer> map=new HashMap<>(); - CSDN文库 

containsKey方法——判断是否包含指定的键名

get() 方法获取指定 key 对应对 value。

get() 方法的语法为:

hashmap.get(Object key)

put() 方法将指定的键/值对插入到 HashMap 中。

put() 方法的语法为:

hashmap.put(K key,V value)
  1. 定义了一个类型为Integer的键和值的Map集合,并初始化为HashMap类型。
  2. 记录当前的目标值的余数
  3. 查找当前的map中是否有满足要求的值
  4. 如果有,返回目标值
  5. 如果没有,把访问过的元素和下标加入map中
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

第454题.四数相加II

力扣题目链接(opens new window)

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间,最终结果不会超过 2^31 - 1 。

例如:

输入:

  • A = [ 1, 2]
  • B = [-2,-1]
  • C = [-1, 2]
  • D = [ 0, 2]

输出:

2

解释:

两个元组如下:

  1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
  2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

视频:《代码随想录》算法视频公开课 (opens new window)学透哈希表,map使用有技巧!LeetCode:454.四数相加II

思路: 

Java中的getOrDefault()方法是Map接口中的一个默认方法,它用于获取指定键的值,如果键不存在,则返回一个默认值。

方法签名: V getOrDefault(Object key, V defaultValue)

参数说明:

  • key:要获取值的键
  • defaultValue:键不存在时返回的默认值

返回值:

  • 如果键存在,则返回与键关联的值;
  • 如果键不存在,则返回默认值。

  1. 首先定义 一个map,key放a和b两数之和,value 放a和b两数之和出现的次数。
  2. 遍历大A和大B数组,统计两个数组元素之和,和出现的次数,放到map中。(map.getOrDefault(sum, 0) + 1中由于第一次运行时并没有sum键是值,故赋值为0并+1之后每次加一就可以统计和为相同的sum的次数,而且在后面的计算判断过程中一定会有:如果一个sum可以满足要求,就可以直接将该sum出现的次数记录用于求有多少个元组 满足要求)
  3. 再遍历大C和大D数组,找到如果 0-(c+d) 在map中出现过的话,就用res把map中key对应的value也就是出现次数统计出来。
  4. 最后返回统计值 res 就可以了
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        //统计两个数组中的元素之和,同时统计出现的次数,放入map
        for (int i : nums1) {
            for (int j : nums2) {
                int sum = i + j;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        //统计剩余的两个元素的和,在map中找是否存在相加为0的情况,同时记录次数
        for (int i : nums3) {
            for (int j : nums4) {
                res += map.getOrDefault(0 - i - j, 0);
            }
        }
        return res;
    }
}


网站公告

今日签到

点亮在社区的每一天
去签到