Continous Subarray Sum


  • 0

    Click here to see the full article post


  • 0
    E

    I'm confused about the 3rd solution. On slide 4: sum is 40 and 40%13 is 1 and not 4 as indicated. Please explain.


  • 0

    @evidanary I have updated the animation. Thanks.


  • 0
    J

    In java, the Map.containsKey ,Map.get and Map.put are not O(1). So I think the time complexity of 3th solution is not O(n).
    And HashMap.containsKey will invoke the similar logic with HashMap.get , so you can use Map.get to get value with specific key, if it is null, the value with specici key is not stored in Map, then just put it, otherwise it exists, just to check it which could avoid one useless get logic in some occassion.
    Thanks.


  • 0

    @jywangkeep In java hashmap get and put takes O(1) with high probability.


  • 0
    J

    I must be missing something. In the first brute force approach, what purpose does having three loops serve?
    isn't it sufficient to use two loops?
    for (int i = 0; i < nums.length; i++) {
    int sum = 0;
    for (int j = i; j < nums.length; j++) {
    sum += nums[j];
    // Check condition
    }
    }
    This would cover all possible contiguous sub-array sums in my mind and offers a O(n) time O(1) space brute-force solution. I must be missing something.


  • 0

    @jj17 It is sufficient to use two loops but brute force approach will be considering the subarray, calculating sum of that subarray and then checking the condition. BTW your solution complexity is O(n^2). Thanks.


  • 0
    J

    Right sorry about that. I meant O(n^2) thanks for the correction!


  • 0
    D

    3rd is not correct, example : 5 0 0 5 , k = 15 please try!


  • 0
    D

    sorry, I forget the case n = 0, you are correct!


  • 0
    C

    could someone please explain the purpose of map.put(0, -1); ?


  • 0
    A

    A little re-phrased and easy to understand.

    class Solution {
    public:
        bool checkSubarraySum(vector<int>& nums, int k) {
            int n=nums.size();
            int i,j;
            if(n<2)
                return false;
            if(k==0){
            for(i=0;i<n;i++)
                 if(nums[i]!=0)
                    return false;
                 return true;
            }
            unordered_set<int> myset;
            int mod,pre=0,sum=0;
            
            for(j=0;j<n;j++){
                sum+=nums[j];
                mod=sum%k;
                if(myset.find(mod)!=myset.end())
                    return true;
                else
                    myset.insert(mod);   
                if(j==0)
                    myset.insert(pre);
            }
            
            return false;
        }
    };
    

  • 0
    E

    @vinod23

    O(min(n,k))O(min(n,k))O(min(n,k)). The HashMap can contain upto min(n,k)min(n,k)min(n,k) different pairings.

    can you explain how it's O(min(n,k) ?


  • 0
    E

    @vinod23

    Space complexity : O(min(n,k))O(min(n,k))O(min(n,k)). The HashMap can contain upto min(n,k)min(n,k)min(n,k) different pairings.

    how is it O(min(n,k) ?


  • 0

    created case [6, 6] for k = 6 result in false, also how should I handle all zero case cause that by means should be multiple of k.


Log in to reply
 

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