Java O(n) explain how I come up with this idea


  • 97

    The subarray sum reminds me the range sum problem. Preprocess the input array such that you get
    the range sum in constant time.
    sum[i] means the sum from 0 to i inclusively
    the sum from i to j is sum[j] - sum[i - 1] except that from 0 to j is sum[j].

    j-i is equal to the length of subarray of original array. we want to find the max(j - i)
    for any sum[j] we need to find if there is a previous sum[i] such that sum[j] - sum[i] = k
    Instead of scanning from 0 to j -1 to find such i, we use hashmap to do the job in constant time.
    However, there might be duplicate value of of sum[i] we should avoid overriding its index as we want the max j - i, so we want to keep i as left as possible.

    public class Solution {
        public int maxSubArrayLen(int[] nums, int k) {
            if (nums == null || nums.length == 0)
                return 0;
            int n = nums.length;
            for (int i = 1; i < n; i++)
                nums[i] += nums[i - 1];
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, -1); // add this fake entry to make sum from 0 to j consistent
            int max = 0;
            for (int i = 0; i < n; i++) {
                if (map.containsKey(nums[i] - k))
                    max = Math.max(max, i - map.get(nums[i] - k));
                if (!map.containsKey(nums[i])) // keep only 1st duplicate as we want first index as left as possible
                    map.put(nums[i], i);
            }
            return max;
        }
    }

  • 1

    OMG this is so smaaaaart!! Thank you you are a life saver today!!!!!


  • 0
    L

    mine is a litter similar, but no extra space for storing sums array and only loops once.
    public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
    if (nums == null || nums.length == 0) {
    return 0;
    }
    int max = 0;
    HashMap<Integer, Integer> hm = new HashMap<>();
    int prevSum = 0;
    hm.put(0, -1);
    for (int i = 1; i <= nums.length; i++) {
    prevSum += nums[i - 1];
    Integer smallIndex = hm.get(prevSum - k);
    if (smallIndex != null) {
    max = Math.max(i - 1 - smallIndex, max);
    }
    if (!hm.containsKey(prevSum)) {
    hm.put(prevSum, i - 1);
    }
    }
    return max;
    }
    }


  • 2
    L

    said in Java O(n) explain how I come up with this idea:

    add this fake entry to make sum from 0 to j consistent

    It would be grateful to get more details about the reasons of "map.put(0, -1);"


  • 1
    N

    @yu-chai1993-outlook-com
    if k is the sum of element from nums[0] to nums[i], the len of subarray is i - 0 + 1.
    in other words, (0, -1) is the initial status.


  • 2
    Y

    @yu-chai1993-outlook-com look at this part max = Math.max(max, i - map.get(nums[i] - k));
    so make map.put(0,-1) is just to say if the nums[i]-k==0 which means index from 0 to index i will make to sum k.
    in this case, the length of the subarray will be 0,1,2,...i, which is i+1, so you need the value of map.get(nums[i]-k) to be "-1"


  • 0
    L

    @xuyirui Lovely. Thanks for explaining how you thought through the solution.


  • 0

    Same idea but only one loop is needed:

    public static int maxSubArrayLen(int[] nums, int k) {
        int index = -1,sum = 0,maxsize = 0;
        HashMap<Integer,Integer> sum_index = new HashMap<Integer,Integer>();
        sum_index.put(0,index);
        while(++index<nums.length){
            sum+=nums[index];
            Integer presumIndex = sum_index.get(sum-k);
            if(presumIndex!=null&&maxsize<index-presumIndex) maxsize = index-presumIndex;
            sum_index.put(sum,sum_index.getOrDefault(sum, index));
        }
        return maxsize;
    }

  • 0
    L

    @NikoBellic thanks! get it!!


  • 0
    L

    @yliang thank you! really clear!


  • 0
    W

    @shuxu said in Java O(n) explain how I come up with this idea:

    public class Solution {
        public int maxSubArrayLen(int[] nums, int k) {
            if (nums == null || nums.length == 0)
                return 0;
            int n = nums.length;
            for (int i = 1; i < n; i++)
                nums[i] += nums[i - 1];
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, -1);  ------------> map.put(k, -1);
                    
            int max = 0;
            for (int i = 0; i < n; i++) {
               // if (map.containsKey(nums[i] - k))
       // why I can't use ?
                  if(k==sum) 
                    max = Math.max(max, i - map.get(nums[i] - k));---->
                    max = Math.max(max, i - map.get(k));
                if (!map.containsKey(nums[i])) 
                    map.put(nums[i], i);
            }
            return max;
        }
    }

  • 0
    S

    Thanks for the smart solution! the "sum[j] - sum[i] = k" helps a lot in my understanding!

    And I also find that in the last for loop, the sequence of adding nums[i] to the map and finding if there is nums[i]-k in the map doesn't matter -- adding nums[i] into the map can always be the first task in every loop.

    Thanks!


Log in to reply
 

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