Description
<nav class="tab-view hide-scrollbar" style="box-sizing: border-box; display: block; overflow-y: hidden; overflow-x: auto; white-space: nowrap; margin-top: 32px;">olution</nav>
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
要好好审题啊！几个重点：
- nums可能有负值
- 所求为连续的subarray
审清题目之后可以发现，我们求的是一段连续的子数组，那么可以用前缀和来得到任意一段子数组。由于前缀和不单调（因为有负值），不能用双指针法，而必须用HashMap来降低时间复杂度。
HashMap, time O(n), space O(n)
sum2FirstIdx.get(s) = i 代表满足nums[0, i) (不含i)的sum为s的最小 i。
注意要提前放入(0, 0)以避免所求subarray是从头开始的情况。
class Solution {
public int maxSubArrayLen(int[] nums, int k) {
Map<Integer, Integer> sum2FirstIdx = new HashMap<>();
int sum = 0;
int maxLen = 0;
sum2FirstIdx.put(0, 0); // in case nums[0, i] is the answer
for (int i = 1; i <= nums.length; ++i) {
sum += nums[i - 1];
if (sum2FirstIdx.containsKey(sum - k)) {
maxLen = Math.max(i - sum2FirstIdx.get(sum - k), maxLen);
}
if (!sum2FirstIdx.containsKey(sum)) {
sum2FirstIdx.put(sum, i);
}
}
return maxLen;
}
}
