help a+b+c+d=0STLvector做，超时了QAQ

Question

P1748 a+b+c+d==0
求和问题可以被看做是以下的公式，给定 A，B，C，D 四个列表，计算有多少四元组满足 (a, b, c, d) ∈ A × B × C × D 且 a + b + c + d = 0。我们推测所有的列表都有 n 个数字。
问题描述：
注：不同的四元组是指元素位置不一样的四元组

数据范围 n<=2e3

样例输入
输入的第一个数字指明有 T 组。每一组这样描述，第一行是列表大小 n， 然后有 n 行。每一行都有四个整型数字，分别属于 A，B，C，D 四列。
1
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

样例输出
5
对于每一个测试用例，统计有多少个四元组满足他们的和是 0 。每一组数据一行。

遇到的问题，超时。

我的思路：将a和b,c和d分别分为一组，计算出ai+bj和ci+dj所有可能的值，并用sum1和sum2进行保存。复杂度为n^2;sort 排序sum2数组复杂度为n^2logn^2;接下来用upp_bound和lower_bound函数找到-sum1[i]在sum2中个数，复杂度为n^2*logn^2。但是最后还是超时了。

我得尝试代码：

#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm> 
using namespace std;
vector<int>v1;
vector<int>v2;
vector<int>v3;
vector<int>v4;
vector<int>sum1;
vector<int>sum2;
int main()
{
    int t=0;
    cin>>t;
    while(t--) //输入复杂度n 
    {
        int n=0;
        cin>>n;
        int a=0,b=0,c=0,d=0;
        for(int i=0;i<n;++i)
        {
            cin>>a>>b>>c>>d;
            v1.push_back(a);
            v2.push_back(b);
            v3.push_back(c);
            v4.push_back(d);    
        }
        
        for(int i=0;i<n;++i)      
        for(int j=0;j<n;++j)  
        {
            sum1.push_back(v1[i]+v2[j]);
        }
        
        for(int i=0;i<n;++i)  
        for(int j=0;j<n;++j)
        {
            sum2.push_back(v3[i]+v4[j]);
        }
        
        sort(sum2.begin(),sum2.end());   
        
        int ans=0;
        vector<int>::iterator s1;
        vector<int>::iterator s2;
        
        for(int i=0;i<sum1.size();++i)
        {
        s1=lower_bound(sum2.begin(),sum2.end(),-sum1[i]);
        s2=upper_bound(sum2.begin(),sum2.end(),-sum1[i]);
        ans+=s2-s1;
      }
        cout<<ans<<endl;
    }
    return 0;
 } 

问题：
根据问题规模2e3;时间复杂度应该不超过n^3;

我的代码根据我上文的尝试分析，实在n^2logn^2级别的，是不应该超时的呀。请大家帮我看看，是否是我的复杂度分析有问题。或者是否有更好的解决方法。orz

Answer 1

该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下：
你的问题在于在每个测试用例中都创建了新的向量，导致内存重新分配和复制，浪费了很多时间。你可以将向量的创建和清空放在 while 循环之外，这样可以避免不必要的内存分配和复制。

此外，你可以使用 unordered_map 或者 unordered_multiset 来优化查找操作。将 sum2 中的值作为 key，将其出现次数作为 value，这样查找 -sum1[i] 在 sum2 中的出现次数可以在常数时间内完成。

下面是经过修改和优化的代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

vector<int> v1, v2, v3, v4;
vector<int> sum1, sum2;

int main() {
  int t;
  cin >> t;

  while (t--) {
    int n;
    cin >> n;

    v1.resize(n);
    v2.resize(n);
    v3.resize(n);
    v4.resize(n);
    sum1.clear();
    sum2.clear();

    for (int i = 0; i < n; ++i) {
      cin >> v1[i] >> v2[i] >> v3[i] >> v4[i];
    }

    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        sum1.push_back(v1[i] + v2[j]);
        sum2.push_back(v3[i] + v4[j]);
      }
    }

    unordered_map<int, int> cnt;
    for (int x : sum2) {
      ++cnt[x];
    }

    int ans = 0;
    for (int x : sum1) {
      ans += cnt[-x];
    }

    cout << ans << endl;
  }

  return 0;
}

注意，unordered_map 在最坏情况下的时间复杂度仍然是 O(n^2)，但是在平均情况下可以达到 O(n) 的时间复杂度，因此可以用来优化查找操作。

---

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢