多多的特殊三元组(C/Py/Java /Js/Go)题解拼多多技术岗 5月17号笔试 第二题题目内容在多多王国的数字世界里多多和我们遇到了一个有趣的数值问题。给定一个整数数组numsnumsnums需要找出所有满足特定条件的特殊三元组。问题描述:特殊三元组定义为满足以下条件的三元组(i,j,k)(i, j, k)(i,j,k)0≤ijklen(nums)0 ≤ i j k len(nums)0≤ijklen(nums)其中nlen(nums)n len(nums)nlen(nums)满足nums[i]nums[k]nums[j]∗2nums[i] nums[k] nums[j] * 2nums[i]nums[k]nums[j]∗2由于答案可能非常大请返回结果对109710^9 71097取余数后的值。输入描述第一行包含一个整数TTT表示测试用例的数量。 每个测试用例的输入如下第一行一个整数nnn表示数组numsnumsnums的长度0≤n≤3000000 ≤ n ≤ 3000000≤n≤300000第二行包含nnn个整数表示数组numsnumsnums的元素−1000000000≤nums[i]≤1000000000-1000000000 ≤ nums[i] ≤ 1000000000−1000000000≤nums[i]≤1000000000输出描述对于每个测试用例输出一个整数表示满足条件的特殊三元组的数量对109710^9 71097取模。样例1输入1 4 0 1 0 0输出1样例2输入1 3 6 3 6输出1样例3输入1 5 8 4 2 8 4输出2题解思路逻辑分析从前往后枚举j 那么该j可以组成的三元组数量等于j左侧值等于num[j]*2 的数量 * j右侧值等于num[j]*2 的数量。按照1的逻辑题目难点主要变成如何快速求出左右侧值nums[j] * 2的数量这部分可以通过使用两个哈希表动态追踪各个值的数量。这部分逻辑可参照下面代码。代码总体时间复杂度为OnC#includebits/stdc.husingnamespacestd;constlongMOD1e97;longsolve(intn,vectorlongnums){// 动态右侧指定数数量unordered_maplong,intrightCount;for(autonum:nums){rightCount[num];}longres0;// 动态追踪左侧指定数数目unordered_maplong,intleftCount;for(autonum:nums){rightCount[num]--;intlleftCount[2*num];intrrightCount[2*num];res(res(l*r)%MOD)%MOD;leftCount[num];}returnres;}intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn;cinn;vectorlongnums(n);for(inti0;in;i){cinnums[i];}coutsolve(n,nums)endl;}}javaimportjava.io.*;importjava.util.*;publicclassMain{staticfinallongMOD1000000007L;staticlongsolve(intn,long[]nums){// 动态右侧指定数数量HashMapLong,IntegerrightCountnewHashMap();for(longnum:nums){rightCount.put(num,rightCount.getOrDefault(num,0)1);}longres0;// 动态追踪左侧指定数数目HashMapLong,IntegerleftCountnewHashMap();for(longnum:nums){rightCount.put(num,rightCount.get(num)-1);intlleftCount.getOrDefault(2*num,0);intrrightCount.getOrDefault(2*num,0);res(res(long)l*r%MOD)%MOD;leftCount.put(num,leftCount.getOrDefault(num,0)1);}returnres;}publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));intTInteger.parseInt(br.readLine());while(T--0){intnInteger.parseInt(br.readLine());String[]strsbr.readLine().split( );long[]numsnewlong[n];for(inti0;in;i){nums[i]Long.parseLong(strs[i]);}System.out.println(solve(n,nums));}}}pythonMOD10**97defsolve(n,nums):# 动态右侧指定数数量right_count{}fornuminnums:right_count[num]right_count.get(num,0)1res0# 动态追踪左侧指定数数目left_count{}fornuminnums:right_count[num]-1lleft_count.get(2*num,0)rright_count.get(2*num,0)res(resl*r)%MOD left_count[num]left_count.get(num,0)1returnres Tint(input())for_inrange(T):nint(input())numslist(map(int,input().split()))print(solve(n,nums))javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,line{input.push(line);});rl.on(close,(){constMOD1000000007n;functionsolve(n,nums){// 动态右侧指定数数量constrightCountnewMap();for(constnumofnums){rightCount.set(num,(rightCount.get(num)||0)1);}letres0n;// 动态追踪左侧指定数数目constleftCountnewMap();for(constnumofnums){rightCount.set(num,rightCount.get(num)-1);constlleftCount.get(num*2)||0;constrrightCount.get(num*2)||0;res(resBigInt(l)*BigInt(r))%MOD;leftCount.set(num,(leftCount.get(num)||0)1);}returnres;}letidx0;constTparseInt(input[idx]);constans[];for(lett0;tT;t){constnparseInt(input[idx]);constnumsinput[idx].split( ).map(Number);ans.push(solve(n,nums).toString());}console.log(ans.join(\n));});Gopackagemainimport(bufiofmtos)constMODint641000000007funcsolve(nint,nums[]int64)int64{// 动态右侧指定数数量rightCount:make(map[int64]int)for_,num:rangenums{rightCount[num]}varresint640// 动态追踪左侧指定数数目leftCount:make(map[int64]int)for_,num:rangenums{rightCount[num]--l:leftCount[2*num]r:rightCount[2*num]res(resint64(l)*int64(r)%MOD)%MOD leftCount[num]}returnres}funcmain(){in:bufio.NewReader(os.Stdin)varTintfmt.Fscan(in,T)for;T0;T--{varnintfmt.Fscan(in,n)nums:make([]int64,n)fori:0;in;i{fmt.Fscan(in,nums[i])}fmt.Println(solve(n,nums))}}