My C++ solution(beats 53.08% cpp of submissions) with explanation


  • 0
    S

    class Solution {
    public:
    vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> output(nums.size(),1);
    for(int i = nums.size()-2; i>=0 ;i--)
    {
    output[i] = output[i+1] * nums[i+1];
    }
    int temp = 1;
    for(int i = 0; i<nums.size();i++)
    {
    output[i] = output[i] * temp;
    temp = nums[i]* temp;
    }
    return output;
    }
    };

    The most important point in this problem I think is the recurrence relation between the adjacent elements.
    For example, in test case [1,2,3,4], for elements '2' and '3', their products of right side of the array are '3*4', which can be denoted as n_2, and '4', which can be denoted as n_3, respectively. We noted that the product n_2 is a recurrence from n_3, by n_3 times the number '3'. So are the same with the products of left side.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.