LeetCode 18-4Sum
来源：4-4 使用查找表的经典问题 Two Sum
stcheng1982
2017-09-25
老师，请教一下LeetCode 18-4Sum 这题。 我提交了后，看到基本大多数的solution还是照着 3sum 那样做的。就是数据先排序， 然后先两重循环确定 前两个数， 然后 用 l，r 指针对撞法来找出 后两个数。这样的solution 时间复杂度我理解是 O（n^3)的。
我除了这种方式，后来尝试另一种方法。数据先排序，然后先是用两层循环把前后不同索引的两个数之和用查找表 dictionary 缓存起来。然后再是一个循环，开始2层和之前那种solution一样确定前2个数，但是到第三层我不用对撞，而是直接从前面的dictionary 中拿出所有 两两相加的和能够和前两层循环中的数一起 加起来==target 的数对，然后把不重复的放入结果。 我的理解，这样的话第三层循环中找的数对应该会比较少。不过实际提交下来，结果不如前一种solution。
不知道我有没有表达清楚， 这两种solution 时间对比应该怎么来看，谢谢。
3回答
-
甲骨文_0001
2023-07-16
var fourSum = function(nums, target) { nums.sort( (a, b)=>a-b ); // 1.计数 let json={}; for( let i = 0; i < nums.length; i ++ ){ json[nums[i]] = json[nums[i]] || 0; json[nums[i]]++; } // 2.相邻去重 let ints=[nums[0]]; let preNum = nums[0]; for( let i = 1; i < nums.length; i ++ ){ if( preNum != nums[i] ){ preNum = nums[i]; ints.push(nums[i]); } } // for i nums = ints; // 存放结果 let res = []; // 3. * 2 for( let i = 0; i < nums.length; i ++ ){ for( let j = i + 1; j < nums.length; j ++ ){ for( let k = j + 1; k < nums.length; k ++ ){ // nums[i] 有多个 if( json[ nums[i] ] > 1 && ( nums[i] * 2 + nums[j] + nums[k] == target ) ){ res.push( [ nums[i], nums[i], nums[j], nums[k] ] ); } // nums[j] 有多个 if( json[ nums[j] ] > 1 && ( nums[i] + nums[j] * 2 + nums[k] == target ) ){ res.push( [ nums[i], nums[j], nums[j], nums[k] ] ); } // nums[k] 有多个 if( json[ nums[k] ] > 1 && ( nums[i] + nums[j] + nums[k] * 2 == target ) ){ res.push( [ nums[i], nums[j], nums[k], nums[k] ] ); } let other = target - nums[i] - nums[j] - nums[k]; if( other > nums[k] && json[other] ){ res.push( [nums[i], nums[j], nums[k], other] ); } } } } // 4. * 3 for( let i = 0; i < nums.length; i ++ ){ for( let j = i + 1; j < nums.length; j ++ ){ // nums[i] 超过3个 if( json[nums[i]] > 2 && ( nums[i] * 3 + nums[j] == target ) ){ res.push( [ nums[i], nums[i], nums[i], nums[j] ] ); } // nums[j] 超过3个 if( json[nums[j]] > 2 && ( nums[i] + nums[j] * 3 == target ) ){ res.push( [ nums[i], nums[j], nums[j], nums[j] ] ); } } } // 5. *2 + *2 for( let i = 0; i < nums.length; i ++ ){ for( let j = i + 1; j < nums.length; j ++ ){ if( json[nums[i]] > 1 && json[nums[j]] > 1 && ( target == nums[i] * 2 + nums[j] * 2 ) ){ res.push( [nums[i], nums[i], nums[j], nums[j]] ); } } } // 6. * 4 for( let i = 0; i < nums.length; i ++ ){ if( json[nums[i]] > 3 && nums[i] * 4 == target ){ res.push( [nums[i], nums[i], nums[i], nums[i]] ); } } return res; };老师，这是我自己的解法，还是用遍历,能通过。只是在尝试用你的哈希表解法时候，没参透48，49两行的奥妙，需要解释下哈：）
042023-07-19 -
stcheng1982
提问者
2017-09-25
public IList<IList<int>> FourSum(int[] nums, int target) { List<IList<int>> results = new List<IList<int>>(); // store results Array.Sort<int>(nums); // sort numbers // use a dictionary to store all possible sums by two distinct numbers (at different position) Dictionary<int, IList<int[]>> s2dict = new Dictionary<int, IList<int[]>>(); for(int i=0;i<nums.Length;++i){ int prev=0; for(int j=i+1;j<nums.Length;++j){ if(j!=i+1 && nums[j]==prev) continue; // for given nums[i], no need to consider duplicated nums[j] (j>i) prev = nums[j]; int s2= nums[i] + nums[j]; if(!s2dict.ContainsKey(s2)) s2dict.Add(s2, new List<int[]>()); s2dict[s2].Add(new int[]{i, j}); } } int prev1=0,prev2=0; for(int i=0;i<nums.Length-3;++i){ if(i!=0 && nums[i] == prev1) continue; prev1 = nums[i]; int tg3 = target-nums[i]; // compute remain target when given nums[i] at first place prev2=0; for(int j=i+1;j<nums.Length-2;++j){ if(j!=i+1 && nums[j]==prev2) continue; prev2 = nums[j]; int tg2 = tg3-nums[j]; // compute remain target when given nums[j] at second place if(s2dict.ContainsKey(tg2)){ // in case there is two numbers' sum which matches the remain target var pairs = s2dict[tg2]; // since in the s2dict, all possible pairs have their first number's index in order, // we can use binary search to get the start position for searching int l=0, r=pairs.Count-1; while(l<=r){ int m= l+(r-l)/2; if(pairs[m][0]>j) r=m-1; else l=m+1; } // if found pairs which have their two number's index after "j"(also after "i") if(l<pairs.Count && pairs[l][0]>j){ HashSet<int> flags = new HashSet<int>(); for(int k=l;k<pairs.Count;++k){ var p = pairs[k]; if(flags.Contains(nums[p[0]])) continue; results.Add(new int[]{nums[i], nums[j], nums[p[0]], nums[p[1]]}); flags.Add(nums[p[0]]); } } } } } return results; }谢谢老师回复。 这是我用C# 写的solution， 有点冗长。 老师有空的时候帮我看一下是哪里没处理好，非常感谢。
012017-09-28 -
liuyubobobo
2017-09-25
你的solution很好。可能是具体实现上产生的效率偏差。如果愿意，可以把你说的O(n^3)的性能高的实现，和你的实现的代码都贴出来，我有时间简单比较一下：）
==== 补充我的实验结果 ====
我用C++将两个思路实现了一遍。基本结果和你差不多。
使用思路1，是O(n^3)的时间复杂度，代码在这里：https://github.com/liuyubobobo/Play-Leetcode/blob/master/old/0018%204Sum/cpp-4Sum/main.cpp
最终结果：
使用思路2，是O(n^2 logn)的时间复杂度，代码在这里：https://github.com/liuyubobobo/Play-Leetcode/blob/master/old/0018%204Sum/cpp-4Sum/main2.cpp
最终结果：
这显然不科学，只有一个可能，leetcode上的测试数据集规模不够。使得算法2的系数和算法1的系数差距显现了出来（还有其他被忽略的低阶复杂度的差距）。类似小样本时，归并排序比插入排序还慢。
于是，我在我的计算机上随机生成了规模是2000的数据，比较两个算法的时间，代码在这里：https://github.com/liuyubobobo/Play-Leetcode/blob/master/old/0018%204Sum/cpp-4Sum/main_compare.cpp
最终结果如下：
我的机子比较慢，相信用更大的数据效果更明显：）
052023-07-16
相似问题