LeetCode刷题实战325：和等于 k 的最长子数组长度
共 4639字，需浏览 10分钟
·
2021-07-18 11:16
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.
示例
示例 1:
输入: nums = [1, -1, 5, -2, 3], k = 3
输出: 4
解释: 子数组 [1, -1, 5, -2] 和等于 3，且长度最长。
示例 2:
输入:nums=[-2, -1, 2, 1],k=1
输出:2
解释:子数组[-1, 2]和等于 1，且长度最长。
解题
暴力破解法：
class Solution {
public int maxSubArrayLen(int[] nums, int k) {
int len = nums.length;
int sum = 0;
int max = 0;
int[] sums = new int[len];
//1.把到目前为止的sum储存进新建的array里，如果有和k相等的sum则与max做比较
for(int i=0; i<len; i++){
sum += nums[i];
sums[i] = sum;
if(sum == k) max = Math.max(max, i+1);
}
//2.对于每一位，从前往后开始一次砍去，如果遇到于sum相等则与max做比较，直接
//break是因为如果找到了后面不可能比前面长
for(int i=0; i<len; i++){
sum = sums[i];
for(int j=0; j<i; j++){
sum -= nums[j];
if(sum == k) {
max = Math.max(max, i-j);//
break;
}
}
}
if(max > 0) return max;
else return 0;
}
}
class Solution {
public int maxSubArrayLen(int[] nums, int k) {
int len = nums.length;
Map<Integer, Integer> map = new HashMap<>();
int sum = 0;
int max = 0;
for(int i=0; i<len; i++){
sum += nums[i];
if(sum == k) max = Math.max(max, i+1);
if(map.containsKey(sum-k)) max = Math.max(max,i-map.get(sum-k));
if(!map.containsKey(sum)) map.put(sum, i);
}
if(max > 0) return max;
else return 0;
}
}