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


  • 87

    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);"


  • 0
    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.


  • 1
    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
    T

    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;
        }
    }

Log in to reply
 

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