Error when using std::vector::size to create another vector-CodePudding

I am learning DSA and while practising my LeetCode questions I came across a question-( https://leetcode.com/problems/find-pivot-index/). Whenever I use vector prefix(size), I am greeted with errors, but when I do not add the size, the program runs fine. Below is the code with the size:

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        //prefix[] stores the prefix sum of nums[]
        vector<int> prefix(nums.size());
        int sum2=0;
        int l=nums.size();
        //Prefix sum of nums in prefix: 
        for(int i=0;i<l;i  ){
            sum2=sum2 nums[i];
            prefix.push_back(sum2);
        }
        //Total stores the total sum of the vector given 
        int total=prefix[l-1];
        for(int i=0; i<l;i  )
        {   
            if((prefix[i]-nums[i])==(total-prefix[i]))
            {
                return i;
            } 
        }
        return -1;
    }
};

I would really appreciate if someone could explain this to me. Thanks!

CodePudding user response：

You create prefix to be the same size as nums and then you push_back the same number of elments. prefix will therefore be twice the size of nums after the first loop. You never access the elements you've push_backed in the second loop so the algorithm is broken.

I suggest that you simplify your algorithm. Keep a running sum for the left and the right side. Add to the left and remove from the right as you loop.

Example:

#include <numeric>
#include <vector>

int pivotIndex(const std::vector<int>& nums) {
    int lsum = 0;
    int rsum = std::accumulate(nums.begin(), nums.end(), 0);

    for(int idx = 0; idx < nums.size();   idx) {
        if(lsum == rsum) return idx;
        lsum  = nums[idx]; // add to the left
        rsum -= nums[idx]; // remove from the right
    }
    return -1;
}

CodePudding user response：

If you use vector constructor with the integer parameter, you get vector with nums.size() elements initialized by default value. You should use indexing to set the elements:

...
for(int i = 0; i < l;   i){
    sum2 = sum2   nums[i];
    prefix[i] = sum2;
}
...

If you want to use push_back method, you should create a zero size vector. Use the constructor without parameters. You can use reserve method to allocate memory before adding new elements to the vector.