Super easy Java Solution without hash map using O(n) time and space


  • 1
    S
    public int maxSubArrayLen(int[] nums, int k) {
            int n = nums.length;
            int max = 0;
            int[] sums = new int[n];// sums[i] stores the sum of subarray starting at i
            for (int i = 0; i < n; i++){
                for (int j = 0; j <= i; j++){
                    sums[j] += nums[i];
                    if (sums[j] == k){
                        max = Math.max(max, i - j + 1);
                    }
                }
            }
            return max;
        }
    

  • 1
    P

    I don't think this is a O(n) solution, with
    for (int i = 0; i < n; i++){
    for (int j = 0; j <= i; j++){
    and no break or continue, it would be an O(n^2) time complexity.


Log in to reply
 

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