企业官网建设流程全解析

多多的特殊三元组(C++/Py/Java /Js/Go)题解

拼多多技术岗 5月17号笔试 第二题

题目内容

在多多王国的数字世界里，多多和我们遇到了一个有趣的数值问题。给定一个整数数组numsnumsnums，需要找出所有满足特定条件的特殊三元组。

问题描述:
特殊三元组定义为满足以下条件的三元组(i,j,k)(i, j, k)(i,j,k)：0≤i<j<k<len(nums)0 ≤ i < j < k < len(nums)0≤i<j<k<len(nums)，其中n=len(nums)n = len(nums)n=len(nums)，满足：nums[i]=nums[k]=nums[j]∗2nums[i] = nums[k] = nums[j] * 2nums[i]=nums[k]=nums[j]∗2
由于答案可能非常大，请返回结果对109+710^9 + 7109+7取余数后的值。

输入描述

第一行：包含一个整数TTT，表示测试用例的数量。 每个测试用例的输入如下：

• 第一行：一个整数nnn，表示数组numsnumsnums的长度（0≤n≤3000000 ≤ n ≤ 3000000≤n≤300000）
• 第二行：包含nnn个整数，表示数组numsnumsnums的元素（−1000000000≤nums[i]≤1000000000-1000000000 ≤ nums[i] ≤ 1000000000−1000000000≤nums[i]≤1000000000）

输出描述

对于每个测试用例，输出一个整数，表示满足条件的特殊三元组的数量（对109+710^9 + 7109+7取模）。

样例1

输入

1 4 0 1 0 0

输出

1

样例2

输入

1 3 6 3 6

输出

1

样例3

输入

1 5 8 4 2 8 4

输出

2

题解

思路

逻辑分析

1. 从前往后枚举j， 那么该j可以组成的三元组数量等于j左侧值等于num[j]*2 的数量 * j右侧值等于num[j]*2 的数量。
2. 按照1的逻辑，题目难点主要变成如何快速求出左右侧值=nums[j] * 2的数量，这部分可以通过使用两个哈希表动态追踪各个值的数量。这部分逻辑可参照下面代码。
3. 代码总体时间复杂度为O（n）

C++

#include<bits/stdc++.h>usingnamespacestd;constlongMOD=1e9+7;longsolve(intn,vector<long>&nums){// 动态右侧指定数数量unordered_map<long,int>rightCount;for(auto&num:nums){rightCount[num]++;}longres=0;// 动态追踪左侧指定数数目unordered_map<long,int>leftCount;for(auto&num:nums){rightCount[num]--;intl=leftCount[2*num];intr=rightCount[2*num];res=(res+(l*r)%MOD)%MOD;leftCount[num]++;}returnres;}intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intn;cin>>n;vector<long>nums(n);for(inti=0;i<n;i++){cin>>nums[i];}cout<<solve(n,nums)<<endl;}}

java

importjava.io.*;importjava.util.*;publicclassMain{staticfinallongMOD=1000000007L;staticlongsolve(intn,long[]nums){// 动态右侧指定数数量HashMap<Long,Integer>rightCount=newHashMap<>();for(longnum:nums){rightCount.put(num,rightCount.getOrDefault(num,0)+1);}longres=0;// 动态追踪左侧指定数数目HashMap<Long,Integer>leftCount=newHashMap<>();for(longnum:nums){rightCount.put(num,rightCount.get(num)-1);intl=leftCount.getOrDefault(2*num,0);intr=rightCount.getOrDefault(2*num,0);res=(res+(long)l*r%MOD)%MOD;leftCount.put(num,leftCount.getOrDefault(num,0)+1);}returnres;}publicstaticvoidmain(String[]args)throwsException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));intT=Integer.parseInt(br.readLine());while(T-->0){intn=Integer.parseInt(br.readLine());String[]strs=br.readLine().split(" ");long[]nums=newlong[n];for(inti=0;i<n;i++){nums[i]=Long.parseLong(strs[i]);}System.out.println(solve(n,nums));}}}

python

MOD=10**9+7defsolve(n,nums):# 动态右侧指定数数量right_count={}fornuminnums:right_count[num]=right_count.get(num,0)+1res=0# 动态追踪左侧指定数数目left_count={}fornuminnums:right_count[num]-=1l=left_count.get(2*num,0)r=right_count.get(2*num,0)res=(res+l*r)%MOD left_count[num]=left_count.get(num,0)+1returnres T=int(input())for_inrange(T):n=int(input())nums=list(map(int,input().split()))print(solve(n,nums))

javascript

constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});constinput=[];rl.on("line",line=>{input.push(line);});rl.on("close",()=>{constMOD=1000000007n;functionsolve(n,nums){// 动态右侧指定数数量constrightCount=newMap();for(constnumofnums){rightCount.set(num,(rightCount.get(num)||0)+1);}letres=0n;// 动态追踪左侧指定数数目constleftCount=newMap();for(constnumofnums){rightCount.set(num,rightCount.get(num)-1);constl=leftCount.get(num*2)||0;constr=rightCount.get(num*2)||0;res=(res+BigInt(l)*BigInt(r))%MOD;leftCount.set(num,(leftCount.get(num)||0)+1);}returnres;}letidx=0;constT=parseInt(input[idx++]);constans=[];for(lett=0;t<T;t++){constn=parseInt(input[idx++]);constnums=input[idx++].split(" ").map(Number);ans.push(solve(n,nums).toString());}console.log(ans.join("\n"));});

Go

packagemainimport("bufio""fmt""os")constMODint64=1000000007funcsolve(nint,nums[]int64)int64{// 动态右侧指定数数量rightCount:=make(map[int64]int)for_,num:=rangenums{rightCount[num]++}varresint64=0// 动态追踪左侧指定数数目leftCount:=make(map[int64]int)for_,num:=rangenums{rightCount[num]--l:=leftCount[2*num]r:=rightCount[2*num]res=(res+int64(l)*int64(r)%MOD)%MOD leftCount[num]++}returnres}funcmain(){in:=bufio.NewReader(os.Stdin)varTintfmt.Fscan(in,&T)for;T>0;T--{varnintfmt.Fscan(in,&n)nums:=make([]int64,n)fori:=0;i<n;i++{fmt.Fscan(in,&nums[i])}fmt.Println(solve(n,nums))}}