Very confused about this topic


  • -1
    X

    I'm not sure why the hint of this problem is dynamic programming. it's a very easy and straightforward plus and plus solution, for each sumRange(i,j), just add from nums[i] to nums[j]. No other guys is aware of this ? my solution beats 100%. it's funny.

    struct NumArray {
    int *nums;
    int numsSize;
    };

    /** Initialize your data structure here. /
    struct NumArray
    NumArrayCreate(int* nums, int numsSize) {

    struct NumArray* na= (struct NumArray*)malloc(sizeof(struct NumArray));
    if(nums==NULL||numsSize==0){
        na->numsSize=0;
        na->nums = NULL;
    }
    na->nums = (int*)malloc(sizeof(int)*numsSize);
    na->numsSize = numsSize;
    for(int i=0;i<numsSize;i++){
        na->nums[i]=nums[i];
    }
    return na;
    

    }

    int sumRange(struct NumArray* numArray, int i, int j)
    {
    if(i<0||j>numArray->numsSize-1) return INT_MIN;

    int start,end;
        
    if(j==i) return numArray->nums[j];
    if(j>i){start = i;end = j;}
    else {start =j;end=i;}
        
    int r = 0;
    for(int k=start;k<=end;k++){
        r += numArray->nums[k]; 
    }
    return r;
    

    }

    /** Deallocates memory previously allocated for the data structure. /
    void NumArrayFree(struct NumArray
    numArray) {
    free(numArray->nums);
    free(numArray);
    }

    // Your NumArray object will be instantiated and called as such:
    // struct NumArray* numArray = NumArrayCreate(nums, numsSize);
    // sumRange(numArray, 0, 1);
    // sumRange(numArray, 1, 2);
    // NumArrayFree(numArray);


  • 0
    P

    It's weird cause your solution is super slow. So probably just an error with OJ.

    Regarding your code, the complexity of sumRange in your code is O(n) when it should be constant speed if you use a caching structure.


  • 0
    X

    Yes, thanks, pisskidney. I got your point and also found the problem I have, I came out another solution with better performance.


Log in to reply
 

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