This is the solution about Leetcode-Maximum Subarray.

Description

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.

Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1:
Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:
Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?

Solution

Analysis

Solution1

  1. Try all possible combinations and get the maximum one.
  2. Time complexity is O(n^2)

Solution2

  1. The main point is we store the sum of 0 - i elements for each location in array. Then we only need to check if sum[j] - sum[i] == k, it represents the sum of i+1 to j.
  2. We use HashMap to get the constant time for the check stuff.
  3. Time complexity is O(n+n+n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution1 {
    public int maxSubArrayLen(int[] nums, int k) {
        int maxLen = 0;
        for(int i=0; i<nums.length; i++) {
            int sum = nums[i];
            if(sum==k) maxLen = Math.max(maxLen,1);
            for(int j=i+1; j<nums.length; j++) {
                sum += nums[j];
                if(sum == k) {
                    maxLen = Math.max(maxLen,j-i+1);
                }
            }
        }
        return maxLen;
    }
}
public class Solution2 {
	public int maxSubArrayLen(int[] nums, int k) {
		int maxLen = 0;
		//in order to preprocess the data easier,assign 0 to sum[0]
		int[] sum = new int[nums.length+1];
		sum[0] = 0;	
		for(int i=1;i<sum.length; i++) {
			sum[i] = sum[i-1] + nums[i-1];
		}
		Map<Integer,Integer> map = new HashMap<>();
		for(int i=0;i<sum.length; i++) {
			map.put(sum[i],i);
		}
		for(int i=0;i<sum.length; i++) {
			Integer val = map.get(sum[i]+k);
			if(val!=null && val.intValue()-i>maxLen) {
				maxLen = val.intValue()-i;
			}
		}
		return maxLen;
	}
}