Ruby Solution O(n), commented code to help with understanding. P100 Ruby


  • 0
    N

    This solution is the P100 of Ruby submissions. That being said, it wasn't meant to be fast but easy to read. I hope the comments make sense. The debug statements are here to help understand what is going on if want to run this code.

    # @param {Integer[]} nums
    # @param {Integer} k
    # @return {Integer}
    def max_sub_array_len(nums, k)
        lookup = {}
        sum = 0
        result = 0
        nums.each_with_index do |num, i|
            # Sum up all values in the nums array
            sum += num
            # This assumes that following occurences of a same sum don't mater
            # since they bring you the same starting point. Since we are trying
            # to get the longuest array we will always want to pick the first one.
            lookup[sum] ||= i
            # How much are we from the sum that we want
            k_delta = sum - k
            #puts "num:#{num} i:#{i} delta:#{k_delta} sum:#{sum}"
            if k_delta == 0
                # If we are exactly at 0 then the whole array from the begining is a match
                # Because we are only incrementing it is impossible for i to be lower than
                # result so we can just overwrite whatever value was there before.
                # Why the +1 ? Because we want the number of element and not the index.
                result = i + 1
                #puts "exact match #{i + 1}"
            elsif lookup.has_key? k_delta
                # If there is a delta between the wanted sum and one we have now we can
                # look in our lookup table for an index that had the exact wanted starting
                # point. At this point we keep the highest value either the previous result
                # or the new greater result.
                #p lookup
                #puts "lookup #{lookup[k_delta]}"
                result = [result, i - lookup[k_delta]].max
            end
        end
        result
    end
    

Log in to reply
 

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