LeetCode454. 四数相加 II

题目

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

分析

关键是如何想到用map，怎么用map？本题目和三数之和、四数之和题目有本质的区别，本题是经典哈希，

而那两道题目是双指针加去重。因为本题实际就是看有多少种满足条件的数组索引组合，和两数之和返回

索引拿到题目用到的知识一样，用map。怎么用？也就是key-value应该保存什么？这就是本题目的重点。

key存放A和B两数组元素之和，value存放这个和出现的次数。然后查找这些中有没有等于-(c+d)的——经典

map查找find。。。。

 1 class Solution {

 2 public:

 3     int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {

 4         unordered_map<int,int>mp;

 5         for(int a : A)

 6             for(int b : B)

 7                 mp[a+b]++;

 8         int count = 0;

 9         for(int c : C)

10             for(int d : D){

11                 if(mp.find(0-(c+d)) != mp.end())

12                     count += mp[0-(c+d)];

13             }

14         return count;

15     }

16 };

总结

我为什么说这题和两数之和那道题异曲同工？发现这题的突破点还是将4个数拆成两组，最后回归到找

map中是否有另一个数。这难道不就是推广了的两数之和吗！！！四个数看成两个数，这道题目就是两

数之和问题，如此破题！

自己还是新手刷的少，开始没思路！以后要经典题目反复刷，就像老唐说的，重点不是做了多少题，而

是做了多少总结！

巴特西

LeetCode454. 四数相加 II

题目

分析

总结

最新文章

热门文章