题目
题目来源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; }
