多约束条件下的元素匹配统计阿里算法岗 0530笔试 第二题题目内容给定三个长度为n nn的数组{ a 1 , a 2 , … , a n } \{a_1, a_2, \dots, a_n\}{a1​,a2​,…,an​}、{ b 1 , b 2 , … , b n } \{b_1, b_2, \dots, b_n\}{b1​,b2​,…,bn​}和{ c 1 , c 2 , … , c n } \{c_1, c_2, \dots, c_n\}{c1​,c2​,…,cn​}。这里c j c_jcj​表示对数组b bb的一个下标。 请你统计满足以下条件的有序对( i , j ) (i, j)(i,j)的数量1 ≤ i ≤ j ≤ n 1 \le i \le j \le n1≤i≤j≤na i b c j a_i b_{c_j}ai​bcj​​。输入描述每个测试文件均包含多组测试数据。第一行输入一个整数T TT1 ≤ T ≤ 2 × 10 5 1 \le T \le 2 \times 10^51≤T≤2×105代表数据组数除此之外保证单个测试文件的n nn之和不超过2 × 10 5 2 \times 10^52×105。 每组测试数据的输入格式如下第一行输入一个整数n nn1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤105第二行输入n nn个整数a 1 , a 2 , … , a n a_1, a_2, \dots, a_na1​,a2​,…,an​1 ≤ a i ≤ 10 9 1 \le a_i \le 10^91≤ai​≤109第三行输入n nn个整数b 1 , b 2 , … , b n b_1, b_2, \dots, b_nb1​,b2​,…,bn​1 ≤ b i ≤ 10 9 1 \le b_i \le 10^91≤bi​≤109第四行输入n nn个整数c 1 , c 2 , … , c n c_1, c_2, \dots, c_nc1​,c2​,…,cn​1 ≤ c j ≤ n 1 \le c_j \le n1≤cj​≤n。输出描述对于每一组测试数据新起一行输出一个整数表示满足条件的有序对数量。样例1输入2 5 1 2 1 2 1 2 1 3 1 2 2 1 5 4 3 3 7 7 7 1 2 7 3 3 3输出5 6题解思路哈希表从前往后枚举j,当前可以组成的合法有序对是a下标为(1, j)中值等于b[c[j]]的数量。按照1的分析并且随着j递增不同数字的数量只会增加不会减少所以可以定义numCount哈希表统计前[1,j]a各种数的数量。从前往后枚举j每次j递增时更新numCount[a[j]]并增加当前j情况下能组成的合法有序对ans numCount[b[c[j]]]C#includebits/stdc.husingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn;cinn;vectorinta(n1),b(n1),c(n1);for(inti1;in;i){cina[i];}for(inti1;in;i){cinb[i];}for(inti1;in;i){cinc[i];}// 记录下标小于j中a每种数字的数量unordered_mapint,intnumCount;intans0;for(intj1;jn;j){numCount[a[j]];ansnumCount[b[c[j]]];}coutansendl;}return0;}javaimportjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intTsc.nextInt();while(T--0){intnsc.nextInt();int[]anewint[n1];int[]bnewint[n1];int[]cnewint[n1];for(inti1;in;i){a[i]sc.nextInt();}for(inti1;in;i){b[i]sc.nextInt();}for(inti1;in;i){c[i]sc.nextInt();}// 记录下标小于j中a每种数字的数量HashMapInteger,IntegernumCountnewHashMap();longans0;for(intj1;jn;j){numCount.put(a[j],numCount.getOrDefault(a[j],0)1);ansnumCount.getOrDefault(b[c[j]],0);}System.out.println(ans);}sc.close();}}pythonfromcollectionsimportdefaultdict Tint(input())for_inrange(T):nint(input())a[0]list(map(int,input().split()))b[0]list(map(int,input().split()))c[0]list(map(int,input().split()))# 记录下标小于j中a每种数字的数量num_countdefaultdict(int)ans0forjinrange(1,n1):num_count[a[j]]1ansnum_count[b[c[j]]]print(ans)javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constlines[];rl.on(line,(line){lines.push(line);});rl.on(close,(){letidx0;constTNumber(lines[idx]);for(lett0;tT;t){constnNumber(lines[idx]);consta[0,...lines[idx].split( ).map(Number)];constb[0,...lines[idx].split( ).map(Number)];constc[0,...lines[idx].split( ).map(Number)];// 记录下标小于j中a每种数字的数量constnumCountnewMap();letans0;for(letj1;jn;j){numCount.set(a[j],(numCount.get(a[j])||0)1);ansnumCount.get(b[c[j]])||0;}console.log(ans);}});Gopackagemainimportfmtfuncmain(){varTintfmt.Scan(T)forT0{T--varnintfmt.Scan(n)a:make([]int,n1)b:make([]int,n1)c:make([]int,n1)fori:1;in;i{fmt.Scan(a[i])}fori:1;in;i{fmt.Scan(b[i])}fori:1;in;i{fmt.Scan(c[i])}// 记录下标小于j中a每种数字的数量numCount:make(map[int]int)varansint640forj:1;jn;j{numCount[a[j]]ansint64(numCount[b[c[j]]])}fmt.Println(ans)}}