文章目录
前言
哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。
这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。
目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为哈希表专题。
题目
题目来源leetcode
leetcode地址：454. 四数相加 II，难度：中等。
题目描述(摘自leetcode)：
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1
提示：
n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
本地调试代码：
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
...
}
public static void main(String[] args) {
int[] nums1 = new int[]{1,2};
int[] nums2 = new int[]{-2,-1};
int[] nums3 = new int[]{-1,2};
int[] nums4 = new int[]{0,2};
System.out.println(new Solution().fourSumCount(nums1, nums2, nums3, nums4));
}
}
题解
NO1：哈希解法
思路： 这里的话给出了四个数组，前两组进行遍历合并存储至map中，key为合并值，value为组数，之后来遍历后两组同样求得0-(合并值)，查看是否在map中存在该key，若是存在表示组合成功，记录组合数量
代码：
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> nums = new HashMap<>(nums1.length*nums1.length);
int temp;
//先对前两组数据进行存储，map中key存储两组数据某个组之和，value存储该组合出现次数
for (int i : nums1) {
for (int j : nums2) {
temp = i + j;
if (nums.containsKey(temp)) {
nums.put(temp, nums.get(temp) + 1);
} else {
nums.put(temp, 1);
}
}
}
//对后两组数据进行统计符合要求的次数
int res = 0;
for (int i : nums3) {
for (int j : nums4) {
temp = i + j;
if (nums.containsKey(0 - temp)) {
res += nums.get(0 - temp);
}
}
}
return res;
}
NO2：手写Map来进行解决（效率最高）
参考大佬leetcode运行效率排名超越100%代码
思路：手写一个专门针对于该题的map，该结构是数组+链表，插入数据采用头插法。实际的思路与NO1相同，时间效率优化主要就是在这个自定义map上。
代码：
//链表节点
private static class Node{
private int val;
private int count;
private Node next;
Node(int val){
this.val = val;
this.count = 1;
}
Node(int val,Node next){
this(val);
this.next = next;
}
}
/**
* Map集合，头插法
*/
private static class Map{
Node[] table;
public Map(int initialCapacity){
if(initialCapacity<16){
initialCapacity = 16;
}else{
//得到小于等于参数的最大2的幂 例如：7=>4，15=>8，17=>16
initialCapacity = Integer.highestOneBit(initialCapacity);
}
table = new Node[initialCapacity];
}
private int hash(int value) {
if (value < 0) {
value = -value;
}
int h;
return (value == 0) ? 0 : (h = value) ^ (h >>> 16);
}
public void put(int val){
int tableIndex = hash(val) & table.length-1;
Node head = table[tableIndex];
//头节点为null情况，直接填充
if(head == null){
table[tableIndex] = new Node(val);
return;
}
//头节点不为null情况，由于其是链表所以需要对其进行遍历比对
Node cur = head;
while(cur != null){
if(cur.val == val){
cur.count++;//若是匹配到了进行加1
return;
}
cur = cur.next;
}
//没有匹配到，采用头插法来插入到当前数组索引下标
table[tableIndex] = new Node(val,head);
}
public int getCount(int val){
int tableIndex = hash(val) & table.length-1;
Node head = table[tableIndex];
if(head == null){
return 0;
}
Node cur = head;
while(cur != null){
if(cur.val == val){
return cur.count;
}
cur = cur.next;
}
return 0;
}
}
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map map = new Map(nums1.length * nums2.length);
int temp;
for (int i : nums1) {
for (int j : nums2) {
temp = i+j;
map.put(temp);
}
}
int res = 0;
for (int i : nums3) {
for (int j : nums4) {
temp = i+j;
if(map.getCount(0-temp) != 0){
res += map.getCount(0-temp);
}
}
}
return res;
}
9
参考文章
[1]. leetcode题解
[2]. 代码随想录— 第454题.四数相加II
我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接
整理者：长路 时间：2021.10.19
评论区请在客户端页面查看