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

Question

问题是我们必须找出是否有任何子数组的总和为 zero.Return 如果可能则为真，否则为假。时间contraint: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 中的 return 值时，您可以同时执行这两项操作。它 return 是一对迭代器（指向元素）和一个 bool 指示元素是否被插入。当 bool 为 false 时，该元素之前已经存在：

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

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

Why my answer is getting accepted with set but not with vector?

c++

arrays

vector

set