一、暴力解***超时:
import java.util.*;
public class Solution {
/**
* max length of the subarray sum = k
* @param arr int整型一维数组 the array
* @param k int整型 target
* @return int整型
*/
public int maxlenEqualK (int[] arr, int k) {
int max = 0;
for (int i =0; i < arr.length; i++) {
int sum = arr[i];
if (sum == k) {
max = Math.max(max, i);
}
for (int j = i + 1; j < arr.length; j++) {
sum += arr[j];
if (sum == k) {
int count = j - i + 1;
max = Math.max(max, count);
}
}
}
return max;
}
}时间复杂度：
空间复杂度：
方法二
思路
哈希
方法一的时间复杂度为，有点慢，处理较大的数据比较吃力，所以需要降低算法的时间复杂度。
其实在方法一中有很多次重复计算，譬如说，在计算了14的连续子数组的累加和后，计算15的连续子数组同样计算了一遍14的累加和，浪费资源，所以需要考虑将之前计算的数据记录下来，以减少之后累加和计算所耗费的时间。i的累加和，S(j)则表示0
令S(i)表示0j的累加和，则j+1i的累加和为S(i)-S(j)。
故可以计算S(i)，并使用hash数组来存储记录S(i)；因为要找出累加和为k的连续子数组，而当前已经知道S(i)，那么我只需要查看hash记录中是否存在S(i)-k这么一个数值，若是存在，则找出出现最早的下标j，
，即连续子数组j+1~i满足题目要求，所以我们只需要依据上述操作，找出所有满足条件的连续子数组，并求出其中的连续最长子数组长度即可。
解法：哈希
假设s(i)是子数组arr[0…i]的累加和,那么s(j)就代表arr[0…j]的累加和，那么可求得arr[j+1…i]=s(i)-s(j)。
流程：
1.初始化变量sum=0，表示从arr[0]一直加到arr[i]的累加和。初始化变量len，表示累加到和为k的最长子数组长度。设置一个map，用来记录出现过的sum值和的它出现的最早位置，即第一次出现的位置。key代表出现过的sum,value代表第一次出现的位置。
令sum+=arr[i]，即s(i)，然后在map中查看是否出现过sum-k。
2.1 如果sum-k存在，则取出它首次出现的位置,假设为j，表示arr[0…j]=sum-k=s(j)。而根据之前的假设arr[j+1…i]=s(i)=s(j),此时sum=s(i),所以arr[j+1…i]=sum-(sum-k)=k。因为map的value记录的是最早出现的位置，所以此时arr[j+1…i]是以arr[i]结尾的所有子数组中，累加和为k的子数组中最长的，然后更新len。
2.2 如果sum-k，不存在，说明以arr[i]结尾的子数组中没有累加和为k的子数组
继续重复2，直到遍历完。
根据arr[j+1…i]=s(i)-s(j),所以，如果从0开始遍历，会导致j+1>=1,这样就会把以arr[0]开始的子数组漏掉了，所以应该从-1位置开始累加，也就是开始遍历时把(0,-1)加入map，表示如果任何一个数都不加时，累加和为0。
比如数组[1,2,3,3],k=6,如果不加（0，-1）：
①sum=1，index=0，加入map，map=[(1,0)];
②sum=3，index=1，加入map，map=[(1,0),(3,1)];
③sum=6，index=2，加入map，map=[(1,0),(3,1),(6,2)];
④sum=9，index=3，此时map包含sum-k，即3，所以此时len的长度更新为2，即子数组为[3,3]。很显然子数组[1,2,3]才是最长的。所以不加（0，-1）会出现这种情况。
如果加了(0,-1):
①sum=1，index=0，加入map,map=[(0,-1),(1,0)];
②sum=3，index=1，加入map，map=[(0,-1),(1,0),(3,1)];
③sum=6，index=2，此时map包含sum-k，即0，此时len的长度为3，即[1,2,3];
④sum=9，index=3，此时map包含sum-k，即3，所以此时子数组为[3,3],长度是2，所以len=3；显然符合要求。
即：
1.设置变量sum = 0，表示从0位置开始一直加到i位置所有元素的和。设置变量len = 0，表示累加和为k的最长子数组长度。设置哈希表map，其中，key表示从arr最左边开始累加的过程中出现过的sum值，对应的value值则表示为sum值最早出现的位置。
2.从左到右遍历，遍历的当前元素为arr[i]，
1）令sum = sum + arr[i],在map中查看是否存在sum-k。
如果sum - k存在，从map中取出sum - k对应的value值，即i - map.get(sum - k)，如果大于 len，则更新len。
如果不存在，说明在必须以arr[i]结尾的情况下没有累加和为k的子数组。
2）检查当前的sum是否在map中，如果不存在，说明此时的sum值是第一次出现的，就把记录 （sum,i）加入到map中。如果sum存在，说明之前已经出现过sum，说明已经出现初sum，map只记录一个累加和最早出现的位置此时什么记录也不添加。
3.继续遍历下一个元素，直到所有元素遍历完。
时间复杂度：
空间复杂度：
import java.util.*;
public class Solution {
/**
* max length of the subarray sum = k
* @param arr int整型一维数组 the array
* @param k int整型 target
* @return int整型
*/
public int maxlenEqualK (int[] arr, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0,-1);
int sum = 0;
int max = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (map.containsKey(sum - k)) {
max = Math.max(max, i -map.get(sum - k));
}
if (!map.containsKey(sum)) {
map.put(sum, i);
}
}
return max;
}
}
京公网安备 11010502036488号