为什么在矢量上使用无序映射会给我一个 TLE？

Question

我正在leetcode上解决这个问题link

这是我使用无序映射的工作解决方案，它为我提供了 TLE，同时使用向量的向量通过了所有测试用例。
它们都按照相同的逻辑工作，那么为什么使用无序映射会给我一个 TLE？

class Solution {
public:
    int longestArithSeqLength(vector<int>& a) {
        
        // vector of umaps
        vector<unordered_map<int, int>> aux(a.size());
        // iterate array
        int n = a.size();
        int ans = INT_MIN;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < i; ++j)
            {
                int currdiff = a[j] - a[i];
                unordered_map<int, int> &umapj = aux[j];
                unordered_map<int, int> &umapi = aux[i];
                
                umapi[currdiff] = umapj[currdiff] + 1;
                
                if(umapi[currdiff] > ans)
                {
                    ans = umapi[currdiff];
                }
            }
        }
        return ans+1;
    }
};

使用向量的代码：

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int n = A.size();
        vector<vector<int>> dp(n, vector<int> (1005, 1));
        int maxLen = 1;
        
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                int d = A[j] - A[i];
                dp[i][d + 500] = dp[j][d + 500] + 1;
                maxLen = max(maxLen, dp[i][d + 500]);
            }
        }
        return maxLen;
    }
};

Answer 1

来自

的最佳答案

首先要注意的是，虽然查询 unordered_map 的平均时间是恒定的，但最坏的情况不是 O(1)。可以看到这里其实上升到了O(N)的量级，N表示容器的大小

其次，由于 vector 分配内存的顺序部分，因此即使在最坏的情况下，对该内存的访问也非常高效并且实际上是恒定的。（即简单的指针算法，而不是计算更复杂的散列函数的结果）还有可能涉及不同级别的顺序内存缓存（即取决于平台，您的代码是运行 on) 与使用 unordered_map.

的代码相比，这可能会使使用 vector 的代码执行得更快

本质上，就复杂度而言，向量的最坏情况性能比unordered_map更有效。最重要的是，大多数硬件系统都提供诸如缓存之类的功能，这使 vector 的使用具有更大的优势。（即 O(1) 操作中较小的常数因子）

为什么在矢量上使用无序映射会给我一个 TLE？

Why does using unordered map over a vector give me a TLE?

c++

vector

time

dynamic-programming

unordered-map