LeetCode 18-4Sum

Question

老师，请教一下LeetCode  18-4Sum 这题。 我提交了后，看到基本大多数的solution还是照着 3sum 那样做的。就是数据先排序， 然后先两重循环确定 前两个数， 然后 用 l，r 指针对撞法来找出 后两个数。这样的solution 时间复杂度我理解是 O（n^3)的。

我除了这种方式，后来尝试另一种方法。数据先排序，然后先是用两层循环把前后不同索引的两个数之和用查找表 dictionary 缓存起来。然后再是一个循环，开始2层和之前那种solution一样确定前2个数，但是到第三层我不用对撞，而是直接从前面的dictionary 中拿出所有 两两相加的和能够和前两层循环中的数一起 加起来==target 的数对，然后把不重复的放入结果。 我的理解，这样的话第三层循环中找的数对应该会比较少。不过实际提交下来，结果不如前一种solution。

不知道我有没有表达清楚， 这两种solution 时间对比应该怎么来看，谢谢。

Answer 1

甲骨文_0001 2023-07-16 02:41:12

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

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两行的奥妙，需要解释下哈：）

• liuyubobobo #1

  我的代码是不是后续有过更改。你再看一下是现在版本的第几行？

• 甲骨文_0001 回复 liuyubobobo #2

  https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0018-4Sum/cpp-0018/main2.cpp,  第50， 51行:  vector<pair<int,int>>::iterator iter =
                          lower_bound(hashtable[t].begin(), hashtable[t].end(), make_pair(nums[j+1], nums[j+1]));

• liuyubobobo 回复 甲骨文_0001 #3

  hashtable[t] 中存的是和为 t 的数字对。注意，因为对 nums 排过序，所以这些数字对是按照 pair 的顺序排的（pair 的第一个元素逐渐增大，在第一个元素相同的情况下，第二个元素逐渐增大）。lower_bound 是 C++ 中封装的二分查找法（有序所以可以使用二分查找），在 hashtable[t] 中寻找第一个大于等于 (nums[j + 1], nums[j + 1]) 的元素，这样确保找到的元素索引不会和当前的 i 和 j 重复。

点开查看后面1条评论

Answer 2

提问者 stcheng1982 2017-09-25 22:04:11

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

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， 有点冗长。 老师有空的时候帮我看一下是哪里没处理好，非常感谢。

• liuyubobobo #1

  我不是特别熟悉C#，不确定是否在语言实现级别应该有大的优化的地方。不过代码整体看了一遍，思路是没有问题的。我也用C++将两个思路实现了一遍，具体结果我更新在我原先的答案里了，希望对你有帮助：）

Answer 3

liuyubobobo 2017-09-25 16:34:40

你的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

最终结果如下：

我的机子比较慢，相信用更大的数据效果更明显：）

• 提问者 stcheng1982 #1

  谢谢老师回复，我重发了个回复，里面贴了代码。

• 提问者 stcheng1982 #2

  非常感谢老师的回复已经细致的测试和分析，我回头也自己测试一下进一步体会一下。

• HuangZhCh #3

  老师，我想请问一下，如果按照这位同学O（n^2logn）复杂度的思路，最后在取出存在dictionary的两个值的时候，怎么保证这两个值的索引，跟前面两重循环确定的值的索引不重复呢？

点开查看后面2条评论