Simple Java, N Pass


  • 0
    S
    public int maxSubArrayLen(int[] nums, int k) {
        int maxLength = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                if((sum += nums[j]) == k) {
                    int length = j - i + 1;
                    if (length > maxLength) {
                        maxLength = length;
                    }
                }
            }
        }
        return maxLength;
    }

  • 0
    S

    I am trying to also figure out what the time complexity is here. I would say O(n^2), but the length of the second loop gets smaller with each iteration of the outer loop. I would want to say O(logn) but even that doesn't sound right since it's not halving the number of iterations... Anyone have any ideas?


  • 0

    Clearly only O(n^2). And not "two pass" but rather "n pass".


  • 0
    S

    Good point, thanks.


Log in to reply
 

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