LeetCode刷题实战325：和等于 k 的最长子数组长度
LeetCode刷题实战325：和等于 k 的最长子数组长度
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 和等于 k 的最长子数组长度，我们先来看题面：
https://leetcode-cn.com/problems/maximum-size-subarray-sum-equals-k/
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.
给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。
注意: nums 数组的总和是一定在 32 位有符号整数范围之内的。
示例
示例 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，且长度最长。解题
https://blog.csdn.net/weixin_39784818/article/details/93567095
暴力破解法：
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;
}
}哈希表：
第一种方法的时间是O(N),主要原因是我们需要找出sum值减多少才能等于目标k，也就是sums[i] - sum[j] = k, 如果我们能用hashMap来储存sum的话，就可以快速找出sums[i] - k的index .
有一个需要注意的点是hashmap里所有的Key值是唯一的，所以需要先用containskey判定是否已经存在，如果存在则不保存，因为对应的value值越小长度越大。
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;
}
}好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
腾讯云开发者
