LeetCode 454. 4Sum II (C++)

标签：题目   cto   遇到   二叉排序树   put   创建   个数   air   结构   题目： Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero. To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1. Example: Input: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] Output: 2 Explanation: The two tuples are: 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0 分析： 问题是给定四个长度相同的数组，在每个数组中取一个元素，所有的组合中和为零的情况有多少种？ 四个数组两两一组，先计算前一组中两个元素的和，存入unordered_map中，再计算另一组中两个数组元素的和的相反数，然后在unordered_map中查找。 程序： class Solution { public: int fourSumCount(vector& A, vector& B, vector& C, vector& D) { unordered_map m; int res = 0; for (auto p:A){ for (auto q:B){ m[p+q]++; } } for (auto i:C){ for (auto j:D){ auto iter = m.find(-i-j); if (iter!=m.end()) res += iter->second; } } return res; } }; 备注: map和unordered_map的差别 1.需要引入的头文件不同 　　map: #include 　　unordered_map: #include 2.内部实现机理不同 　　map：map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相 当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。 　　unordered_map：unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。 3.优缺点以及适用处 　　map优点：有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作。红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高。 　　map缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间。 　　map适用处：对于那些有顺序要求的问题，用map会更高效一些。 　　unordered_map优点： 因为内部实现了哈希表，因此其查找速度非常的快。 　　unordered_map缺点： 哈希表的建立比较耗费时间。 　　unordered_map适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map。4.总结： 　　内存占有率的问题就转化成红黑树 VS hash表 , 还是unorder_map占用的内存要高。 　　但是unordered_map执行效率要比map高很多。 　　对于unordered_map或unordered_set容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的。 5.map和unordered_map的使用 　　unordered_map的用法和map是一样的，提供了 insert，size，count等操作，并且里面的元素也是以pair类型来存贮的。其底层实现是完全不同的，上方已经解释了，但是就外部使用来说却是一致的。 参考：https://blog.csdn.net/BillCYJ/article/details/78985895LeetCode 454. 4Sum II (C++)标签：题目   cto   遇到   二叉排序树   put   创建   个数   air   结构   原文地址：https://www.cnblogs.com/silentteller/p/10224311.html