• 欢迎光临~

LeetCode 454 4Sum II

开发技术 开发技术 2022-08-02 次浏览

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

  • (0 le i, j, k, l < n)
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Solution

改写一下得到:

[nums1[i]+nums2[j]=-(nums3[k]+nums4[l]) ]

那么直接用 (map) 即可,复杂度 (O(n^2))

点击查看代码
class Solution {
private:
    int ans = 0;
    map<int,int> mp;
    
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int n = nums1.size();
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                mp[nums1[i]+nums2[j]]++;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                ans+=mp[-nums3[i]-nums4[j]];
            }
        }
        return ans;
    }
};
程序员灯塔
转载请注明原文链接:LeetCode 454 4Sum II
喜欢 (0)