LeetCode 18-4Sum-慕课网

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

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

0 回复有任何疑惑可以回复我~

收起回答

liuyubobobo #1

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

回复有任何疑惑可以回复我~ 2023-07-18 00:54:34

甲骨文_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]));

回复有任何疑惑可以回复我~ 2023-07-18 11:20:12

liuyubobobo 回复甲骨文_0001 #3

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

回复有任何疑惑可以回复我~ 2023-07-19 01:58:29

点开查看后面1条评论

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

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

0 回复有任何疑惑可以回复我~

收起回答

liuyubobobo #1

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

回复有任何疑惑可以回复我~ 2017-09-28 13:44:16

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

最终结果如下：

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

0 回复有任何疑惑可以回复我~

收起回答

提问者 stcheng1982 #1
```
谢谢老师回复，我重发了个回复，里面贴了代码。
```
回复有任何疑惑可以回复我~ 2017-09-25 22:04:52

提问者 stcheng1982 #2

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

回复有任何疑惑可以回复我~ 2017-09-28 14:00:37

HuangZhCh #3

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

回复有任何疑惑可以回复我~ 2017-10-12 13:14:14

点开查看后面2条评论

LeetCode 18-4Sum

正在回答回答被采纳积分+3

3回答

相似问题

请选择置顶位置

本课精华内容

关于leetcode309题的一个小疑惑（java）

请问这两个memo[i]有什么区别？为什么要这样写?比如i=2时，右边那个memo[i]不是没有初值吗？怎么比较？

Leetcode 864疑问

二分查找法floor和ceil的边界问题

LeetCode 18-4Sum

更多经典面试问题

动态规划的经典问题

不会翻转二叉树的大神

两种关于 topK 问题求解思路的套路

大厂面试为什么总考算法？

热搜

最近搜索清空

LeetCode 18-4Sum

正在回答 回答被采纳积分+3

3回答

相似问题

请选择置顶位置

本课精华内容

关于leetcode309题的一个小疑惑（java）

请问这两个memo[i]有什么区别？为什么要这样写?比如i=2时，右边那个memo[i]不是没有初值吗？怎么比较？

Leetcode 864疑问

二分查找法floor和ceil的边界问题

LeetCode 18-4Sum

更多经典面试问题

动态规划的经典问题

不会翻转二叉树的大神

两种关于 topK 问题求解思路的套路

大厂面试为什么总考算法？

正在回答回答被采纳积分+3