My code:
public class Solution {
public int maxSubArrayLen(int[] nums, int k) {
if (nums == null || nums.length == 0)
return 0;
int max = 0;
HashMap<Integer, Integer> tracker = new HashMap<Integer, Integer>();
int sum = 0;
tracker.put(0, -1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (!tracker.containsKey(sum)) {
tracker.put(sum, i);
}
if (tracker.containsKey(sum - k)) {
int pre = tracker.get(sum - k);
max = Math.max(max, i - pre);
}
}
return max;
}
}
这道题目可以作为这类题目的通解。
找一段区域中数组的和,要达到某种要求,比如,等于k
参考网页:
http://www.cnblogs.com/EdwardLiu/p/5104280.html
Anyway, Good luck, Richardo!
My code:
import java.util.HashMap;
public class Solution {
public int maxSubArrayLen(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] sum = new int[n];
int cum = 0;
for (int i = 0; i < n; i++) {
cum += nums[i];
sum[i] = cum;
}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(k, -1);
int max = 0;
for (int i = 0; i < sum.length; i++) {
if (map.containsKey(sum[i])) {
int index = map.get(sum[i]);
max = Math.max(max, i - index);
}
int target = sum[i] + k;
if (!map.containsKey(target)) {
map.put(sum[i] + k, i);
}
}
return max;
}
public static void main(String[] args) {
Solution test = new Solution();
int[] nums = new int[]{1,-1,5,-2,3};
int ret = test.maxSubArrayLen(nums, 3);
System.out.println(ret);
}
}
这道题目自己做了出来。
其实就是先构造一个累加数列。然后做一个 two sum
当我到达 sum[i]时,如果有 sum[j] + k = sum[i]
那么, [ j + 1, i ] 的和一定是 k
所以用一个 HashTable 用来存 target 的值。和 2Sum一个原理。
Anyway, Good luck, Richardo! -- 09/21/2016