Leetcode 454. 四数相加 II（DAY 151） ---- LeetCode 精选 TOP 面试题

今天药忘吃喽~ 2022-09-07 09:49 145阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷未优化版 C++）
     *  代码实现（首刷优化版）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]

--------------------

## 代码实现（首刷未优化版 C++） ##

--------------------

class Solution { 
    public:
        void calc(unordered_map<int,int>& map,vector<int>& n1,vector<int>& n2)
        { 
            for(int i=0;i<n1.size();++i)
            { 
                int num = n1[i];
                for(int j=0;j<n2.size();++j)
                    ++map[num+n2[j]];
            }
        }
    
        int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { 
            vector<unordered_map<int,int>> v(2);
            int ret = 0;
            calc(v[0],nums1,nums2);
            calc(v[1],nums3,nums4);
                for(const auto& pair:v[0])
                    ret += v[1][-pair.first] * pair.second; 
            
            return ret;
        }
    };

--------------------

## 代码实现（首刷优化版） ##

--------------------

class Solution { 
    public:
    
        int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { 
            unordered_map<int,int> map;
            int ret = 0;
            for(const auto& n1:nums1)
                for(const auto& n2:nums2)
                    ++map[n1+n2];
            
            for(const auto& n3:nums3)
                for(const auto& n4:nums4)
                    ret += map[-(n3+n4)];
            
            return ret;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]: /images/20220829/26caf4060b3445f6a6403c36e7536629.png