0小明的数组游戏

0小明的数组游戏 - 蓝桥云课

问题描述

今天小明获得了三个长度为 n 的数组，分别为 a,b,c，小明盯着这三个数组看了半天，脑子里渐渐产生了一个想法，我能否知道这三个数组中有多少对三元组下标 {i,j,k} 满足 ai​+bj​+ck​=m，并要求在短时间内得到自己想要的答案，聪明的你能够帮帮小明吗。

输入格式

第一行，包含两个正整数 n,m（1≤n≤1e3）（1≤m≤3×1e9），代表这三个数组的长度为 n。

第二行，包含 n 个正整数 ai​（1≤ai​≤1e9），代表数组 a 中的元素。

第三行，包含 n 个正整数 bi​（1≤bi​≤1e9），代表数组 b 中的元素。

第四行，包含 n 个正整数 ci​（1≤ci​≤1e9），代表数组 c 中的元素。

输出格式

一行，包含一个正整数，为最终答案，这三个数组中有多少个三元组 {i,j,k} 满足 ai​+bj​+ck​=m。

样例输入

3 13
1 2 3
4 5 6
7 8 9

样例输出

3

样例说明

在样例中，符合条件的三元组为 {1,2,1}，{1,1,2}，{2,1,1}，他们的和都为 13，可以证明没有更多的三元组满足条件。

思路:
我们可以知道n的长度只有1e3，说明O（n*n）不会超时，那么按暴力思维来看，这题需要三个for必定超时，那么我们就需要优化。我们可以组合i，j序列，利用哈希思维求三元组个数。

代码如下：
 

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const ll N = 1e3+10;
ll n,m; 
ll a[N];
ll b[N];
ll c[N];
int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(ll i = 1 ; i <= n ; i++)
	cin >> a[i];
	for(ll i = 1 ; i <= n ; i++)
	cin >> b[i];
	for(ll i = 1 ; i <= n ; i++)
	cin >> c[i];
	map <int,int> mp;
	for(ll i = 1 ; i <= n ; i++)
	{
		for(ll j = 1 ; j <= n ; j++)
		{
			mp[a[i]+b[j]]++;
		}
	}
	ll sum = 0;
	for(ll i = 1 ; i <= n ; i++)
	{
		sum = sum + mp[m - c[i]];
	}
	cout << sum;
    return 0;
}