leetcode 454. 4Sum II | 454. 四数相加 II（Java）

小灰灰 2022-09-06 04:58 101阅读 0赞

## 题目 ##

[https://leetcode.com/problems/4sum-ii/][https_leetcode.com_problems_4sum-ii]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

四数相加问题。

对于左边两个数两两组合，需要维护一个 map，用来存左边两个数的 sum 以及该 sum 对应的 count。

对于右边两个数两两组合，需要查 map 中是否有可以与之匹配的元素。如果有，将个数累加到 count 中。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

class Solution { 
        public int fourSumCount(int[] n1, int[] n2, int[] n3, int[] n4) { 
            HashMap<Integer, Integer> map = new HashMap<>(); //(sum,count)
            
            int n = n1.length;
            for (int i = 0; i < n; i++) { 
                for (int j = 0; j < n; j++) { 
                    int sum = n1[i] + n2[j];
                    if (!map.containsKey(sum)) map.put(sum, 0);
                    map.put(sum, map.get(sum) + 1);
                }
            }
    
            int count = 0;
            for (int i = 0; i < n; i++) { 
                for (int j = 0; j < n; j++) { 
                    int sum = -n3[i] - n4[j];
                    if (map.containsKey(sum)) count += map.get(sum);
                }
            }
            return count;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_4sum-ii]: https://leetcode.com/problems/4sum-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/88e101668ae745aea19e0fecea0805a0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/e1c01bde0421472096f38c8bf8187e65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/9221cdc3d0374672a42a153c55d98e73.png