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

Question is We have to find if there is any sub array whose sum is zero.Return true if possible and false if not. Time contraint:3 seconds

This is the code using unordered set getting accepted .

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;
    }

This is the vector solution which is giving 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;
    }

CodePudding user response：

This line

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

is very different from this line

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

First, a unordered_set does not store the same element twice. In general this would make a difference, though as you stop when you encounter the first duplicate, the number of elements in the vector and in the set are the same here.

Next, std::unordered_set::find has average constant complexity while std::find is linear. std::unordered_set::find can make use of the internal structure of the set, thats why it exists in the first place. You don't want to use std::find with a set, because that would be less performant. With the set your algorithm is O(N) with the vector it is O(1 2 3 ... N) which is O(N^2).

Note that the version with the set could be made even faster. Currently you are searching the element twice. Once here s.find(sum) and another time when inserting it. You could do it both at once when you use the return value from unodered_set::insert. It returns a pair of an iterator (pointing to the element) and a bool that indicates whether the element was inserted. When that bool is false, the element was already present before:

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