当前位置: 首页> 教育> 就业 > 名片制作app软件_免费学习网_seo在线培训机构_百度推广入口官网

名片制作app软件_免费学习网_seo在线培训机构_百度推广入口官网

时间:2025/7/10 17:31:42来源:https://blog.csdn.net/Mwt258/article/details/142786165 浏览次数:0次
名片制作app软件_免费学习网_seo在线培训机构_百度推广入口官网

【算法系列-哈希表】两数之和 (Map)

文章目录

  • 【算法系列-哈希表】两数之和 (Map)
    • 1. 两数之和(LeetCode 1, 梦开始的地方)
      • 1.1 思路分析🎯
      • 1.2 解题过程🎬
      • 1.3 代码示例🌰
    • 2. 四数相加II(LeetCode 454)
      • 2.1 思路分析🎯
      • 2.2 解题过程🎬
      • 2.3 代码示例🌰

1. 两数之和(LeetCode 1, 梦开始的地方)

【题目链接】1. 两数之和 - 力扣(LeetCode)

1.1 思路分析🎯

这道题使用哈希表中的map结构来解决问题,不过开始之前我们需要理清楚为什么要使用哈希表:

什么时候用哈希表:当我们需要判断一个元素之前是否出现过 或 一个元素是否存在于一个集合中时,可以使用哈希表;
这道题中我们需要哈希表来帮我们记录已经遍历过的元素;

为什么要使用map:这道题中我们返回的结果是元素在数组中的索引下标,对此可以使用map来进行映射,key存储元素,value存储索引下标

理清楚上述关系后就可以开始解题了

1.2 解题过程🎬

定义一个map,key存储元素,value存储索引下标 遍历数组:通过目标值target 减去当前数组下标元素 x1,得到数值x2,之后判断map中是否存在x2:

存在,则返回当前循环的索引值 i 以及 key = x2在map中的value值

不存在,则将当前数组下标元素x1 加入map中,继续循环

直到循环结束仍未返回,则返回空集合

1.3 代码示例🌰

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0;i < nums.length;i++) {int x1 = nums[i];int x2 = target - x1;if (map.containsKey(x2)) {return new int[]{i, map.get(x2)};}map.put(x1, i);}return new int[2];}
}

2. 四数相加II(LeetCode 454)

【题目链接】454. 四数相加 II - 力扣(LeetCode)

2.1 思路分析🎯

这道题若用暴力解决的话,会直接**超时 O(n^4)**了,如下:

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int count = 0;for (int i = 0;i < nums1.length;i++) {for (int j = 0;j < nums2.length;j++) {for (int x = 0;x < nums3.length;x++) {for (int y = 0;y < nums4.length;y++) {if (nums1[i] + nums2[j] + nums3[x] + nums4[y] == 0) {count++;}}}}}return count;}
}

在这里插入图片描述

所以使用哈希表来降低时间复杂度

2.2 解题过程🎬

定义 map 用来记录 数组1 和 数组2 遍历过的元素,key 为 两个数组元素每轮遍历元素之和,value 为两个数组元素之和出现的次数,之后分别执行下述操作:

  • 先对 数组 nums1 和 数组 nums2 进行遍历,设 a 为 nums1中元素, b 为 nums2 中元素,将 a + b 添加到map中;
  • 后对 数组 nums3 和 数组 nums4 进行遍历,设 c 为 nums3中元素, d 为 nums4 中元素,将 n = 0 - (c + d)添加到map中;若 n 在map中存在,则 count += map.get(n)

: 这里之所以是 0 - (c+ d) 是因为我们需要将这个元素和拿到map中去进行匹配,而 0 - (c + d) = (a + b) ); 这里是 + map.get(n) 而不是count++ 是因为 n 可以与 a + b 进行组合,所以要加上对应的次数

直到循环结束返回count即可

2.3 代码示例🌰

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int count = 0;Map<Integer, Integer> map = new HashMap<>();for (int a : nums1) {for (int b : nums2) {map.put(x + y, map.getOrDefault(a + b, 0) + 1);}}for (int c : nums3) {for (int d : nums4) {int n = 0 - (c + d);if (map.containsKey(n)) {count += map.get(n);}}}return count;}
}

以上便是对两数之和类问题的介绍了!!后续还会继续分享其它算法系列内容,如果这些内容对大家有帮助的话请给一个三连关注吧💕( •̀ ω •́ )✧( •̀ ω •́ )✧✨

关键字:名片制作app软件_免费学习网_seo在线培训机构_百度推广入口官网

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: