C++ 数组配对查询 - 查找满足特定条件的元素对

{"title":"You have an array a\nof length n.\n\nYour task is to answer q\nqueries: given x,y\n, find the number of pairs i\nand j\n (1≤i<j≤n\n) that both ai+aj=x\nand ai⋅aj=y\n.\n\nThat is, for the array [1,3,2]\nand asking for x=3,y=2\nthe answer is 1\n:\n\ni=1\nand j=2\nfail because 1+3=4\nand not 3,\nalso 1⋅3=3\nand not 2\n;\ni=1\nand j=3\nsatisfies both conditions;\ni=2\nand j=3\nfail because 3+2=5\nand not 3,\nalso 3⋅2=6\nand not 2\n;\nInput\nThe first line contains one integer t\n (1≤t≤104\n) — the number of test cases.\n\nThe second line of each test case contains one integer n\n (1≤n≤2⋅105\n) — the length of the array a\n.\n\nThe third line of each test case contains n\n integers a1,a2,…,an\n (1≤|ai|≤109\n) — array a\n.\n\nThe fourth line of each test case contains the integer q\n (1≤q≤2⋅105\n) — the number of requests.\n\nThe next q\n lines contain two numbers each x\n and y\n (1≤|x|≤2⋅109,1≤|y|≤1018\n) — request.\n\nIt is guaranteed that the sum of n\n over all test cases does not exceed 2⋅105\n. This is also guaranteed for the sum of q\n values.\n\nOutput\nFor each test case print a line with q\n numbers — the answers to the queries.c++代码内容：Here is a possible implementation in C++:\n\ncpp\n#include <iostream>\n#include <vector>\n#include <unordered_map>\n\nusing namespace std;\n\nint main() {\n int t;\n cin >> t;\n\n while (t--) {\n int n;\n cin >> n;\n\n vector<int> a(n);\n for (int i = 0; i < n; i++) {\n cin >> a[i];\n }\n\n int q;\n cin >> q;\n\n while (q--) {\n int x, y;\n cin >> x >> y;\n\n unordered_map<int, int> freq;\n int count = 0;\n\n for (int i = 0; i < n; i++) {\n int ai = a[i];\n int aj = x - ai;\n\n if (freq.count(aj)) {\n count += freq[aj];\n }\n\n freq[ai]++;\n }\n\n cout << count << " ";\n }\n\n cout << endl;\n }\n\n return 0;\n}\n\n\nExplanation:\n- We start by reading the number of test cases t from the input.\n- We then iterate t times, each time reading the length of the array n, the array a, the number of queries q, and the queries themselves.\n- For each query, we create a frequency map freq to keep track of the occurrences of each element in the array.\n- We initialize a variable count to keep track of the number of pairs satisfying the conditions.\n- We iterate over each element ai in the array and calculate the corresponding aj such that ai + aj = x.\n- If aj exists in the frequency map, we add the frequency of aj to the count.\n- We then update the frequency of ai in the map.\n- Finally, we output the count for each query and move to the next test case.\n\nThis solution has a time complexity of O(t * (n + q)), where t is the number of test cases, n is the length of the array, and q is the number of queries.