前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 454. 四数相加 II(哈希)

LeetCode 454. 四数相加 II(哈希)

作者头像
Michael阿明
发布2020-07-13 15:24:42
2230
发布2020-07-13 15:24:42
举报
文章被收录于专栏:Michael阿明学习之路

1. 题目

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间,最终结果不会超过 231 - 1 。

类似题目:POJ 2785

2. 解题

  • 二分查找,最后一个例子超时
在这里插入图片描述
在这里插入图片描述
代码语言:javascript
复制
class Solution {
	int *ab, *cd;
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        int n = A.size(), i, j, k = 0, ans = 0;
        int N = n*n;
        ab = new int[N];
        cd = new int[N];
        for(i = 0; i < n; ++i)
        	for(j = 0; j < n; ++j)
        		ab[k++] = A[i]+B[j];
    	k = 0;
    	for(i = 0; i < n; ++i)
        	for(j = 0; j < n; ++j)
        		cd[k++] = -C[i]-D[j];
        sort(cd,cd+N);
        for(i = 0; i < N; ++i)
        {
        	ans += findV(ab[i], N);
        }
        return ans;
    }
    int findV(int &val, int &N)
    {
    	int i = 0, j = N-1, mid, count = 0, idx;
    	while(i <= j)
    	{
    		mid = i+((j-i)>>1);
    		if(val == cd[mid])
    		{
    			idx = mid-1;
    			while(idx >= 0 && cd[idx--] == val)
    				++count;
    			idx = mid+1;
    			while(idx < N && cd[idx++] == val)
    				++count;
    			return count+1;
    		}
    		else if(val < cd[mid])
    			j = mid-1;
    		else
    			i = mid+1;
    	}
    	return 0;
    }
};
  • 哈希表
代码语言:javascript
复制
class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        int n = A.size(), i, j, ans = 0;
        unordered_map<int, int> m;
        for(i = 0; i < n; ++i)
        	for(j = 0; j < n; ++j)
        		if(m.find(A[i]+B[j]) == m.end())
        			m[A[i]+B[j]] = 1;
        		else
        			m[A[i]+B[j]]++;
    	for(i = 0; i < n; ++i)
        	for(j = 0; j < n; ++j)
        		if(m.find(-C[i]-D[j]) != m.end())
        			ans += m[-C[i]-D[j]];
        return ans;
    }
};
在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/10/07 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 解题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档