为什么我的答案被 set 接受但不被 vector 接受？

Question

问题是我们必须查找是否存在总和为零的子数组。如果可能则返回 true，否则返回 false。 时间限制：3秒

这是使用无序集被接受的代码。

bool subArrayExists(int arr[], int n)
    {
        //Your code here
        int sum=0;
        unordered_set<int>s;
        for(int i=0;i<n;i++){
            sum=sum+arr[i];
            if(sum==0||s.find(sum)!=s.end()){
               return true;
            }
            s.insert(sum);
        }
        return false;
    }

这是给出 tle 的向量解。

bool subArrayExists(int arr[], int n)
    {
        //Your code here
        int sum=0;
        vector<int>v;
        for(int i=0;i<n;i++){
            sum=sum+arr[i];
            if(sum==0||find(v.begin(),v.end(),sum)!=v.end()){
                return true;
            }
            v.push_back(sum);
        }
        return false;
    }

Answer 1

这一行

if(sum==0||s.find(sum)!=s.end()){

与这一行非常不同，

if(sum==0||find(v.begin(),v.end(),sum)!=v.end()){

首先，unordered_set 不会存储相同的元素两次。一般来说，这会产生影响，尽管当您遇到第一个重复项时停止，向量和集合中的元素数量在这里是相同的。

接下来，std::unordered_set::find 具有平均恒定复杂度，而 std::find 是线性的。 std::unordered_set::find 可以利用集合的内部结构，这就是它存在的原因。您不想将 std::find 与无序集一起使用，因为那样会降低性能。对于无序集，您的算法为 O(N)，向量为 O(1 + 2 + 3 + ... + N)，即 O (N^2)。

请注意，具有无序集的版本可以做得更快。目前您正在搜索该元素两次。一次是在这里 s.find(sum) ，另一次是在插入它时。当您使用 unodered_set::insert 的返回值时，您可以同时执行这两项操作。它返回一对迭代器（指向元素）和一个指示元素是否已插入的布尔值。当该 bool 为 false 时，该元素之前已经存在：

        sum=sum+arr[i];
        auto ret = s.insert(sum);
        if(sum==0 || ret.second == false){
           return true;
        }