四数相加 II

谁借莪１个温暖的怀抱￠ 2022-12-24 09:58 119阅读 0赞

> leetcode 454题 \[medium\]  
> 中：[四数相加 II][II]  
> 英：[4Sum II][]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]

### 题解 ###

1.  **四数之和问题** 转为 **两个两数之和的求和问题**  
    （1）将四个数组分为两组，每组两个数组。对于每组的两个数组，分别记录其求和的各种和值及相应的组合数。  
    （2）最后问题就转为，对这两个求和记录再次进行求和，记录使得求和结果为0的组合数。
2.  优化  
    （1）只需记录一个组合的结果即可，另一个组合直接在遍历构建的过程中使用第一个组合的结果进行**和零**的判断  
    （2）第一个组合的键直接记录和值的相反数  
    （3）使用 `Map` 代替 `Object`
3.  复杂度  
    （1）时间：O(n²) 未记数据存储到Map中的复杂度  
    （2）空间：O(n²) 最坏情况是所有和值都不相同
4.  实现
    
        /** * @param {number[]} A * @param {number[]} B * @param {number[]} C * @param {number[]} D * @return {number} */
        var fourSumCount = function(A, B, C, D) { 
            // 预处理（无）
        
            // 键：和值； 值：有几种情况
            let ABDict = new Map();     // 存储AB的和值组合，键为和值的相反数，值为出现这种和值的组合数
            let result = 0;             // 结果
            let len = A.length;         // 缓存length
            // 构建ABDict
            for(let i=0; i<len; i++){ 
                for(let j=0; j<len; j++){ 
                    let sum = A[i] + B[j];
                    ABDict.set(-sum, ((ABDict.get(-sum) || 0) + 1));
                }
            }
            // 遍历CD和值的各种情况，且若这种和值能在ABDict的键中找到（ABDict的键为AB和值的相反数），则把AB出现这种和值相反数的组合数累加到result中
            for(let i=0; i<len; i++){ 
                for(let j=0; j<len; j++){ 
                    result += (ABDict.get(C[i] + D[j]) || 0);
                }
            }
        
            return result;
        };

[II]: https://leetcode-cn.com/problems/4sum-ii/
[4Sum II]: https://leetcode.com/problems/4sum-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]: /images/20221120/62854130ac184f53ab256e00ed915c0b.png