题解 | #未排序数组中累加和为给定值的最长子数组长度#

问题描述：给定一个无序数组arr, 其中元素可正、可负、可0。给定一个整数k，求arr所有子数组中累加和为k的最长子数组长度

示例

输入：[1,-2,1,1,1],0

返回值：3

说明：最长子数组为[1,-2,1]，其长度为3

本题我们能直接想到的办法就是暴力穷举，外层循环从数组开始位置遍历，内层循环遍历从上一层的位置开始，使用sum记录当前数组的和，如果达到k，将数组长度记录下来，之后继续向后遍历，当内层循环遍历到数组结束位置后，外层循环往下继续刚才的操作。这种方法时间复杂度较大。因此我们考虑使用前缀和数组，定义数组$pre[i]=arr[0]+arr[1]+...+arr[i-1]$，那么子数组$arr[i]$到$arr[j-1]$的和为$pre[j]-pre[i]$而后计算出所有可能的前缀和数组，特别的数组中第一个元素的前缀和初始化为0，接着我们根据子数组的可能的长度，按长度的最大值开始向下遍历，即按照数组长度由大到小找到原数组中可能的子数组，如果子数组的和$pre[j]-pre[i]$为k,则输出当前的子数组长度。

输入：[1,-2,1,1,1],0

首先计算其前缀数组$pre[6]=\{0,1,-1,0,1,2\}$

$len$	子数组的起止位置$i$	子数组的和
5	0	$presum[0+5]-presum[0]=2$
4	0	$presum[0+4]-presum[0]=1$
	1	$presum[1+4]-presum[1]=1$
3	0	$presum[0+3]-presum[0]=0$ $k=0$程序在此处运行结束
	1
	2

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 n=arr.length;
        int[] presum=new int[n+1];
        for(int i=0;i<n;i++){
            presum[i+1]=presum[i]+arr[i];////构建前缀和数组，开始元素的前缀和为0，因此设置n+1个长度
        }

        //逆序遍历所有可能的长度
        for(int len=n;len>=1;len--)
		{
            for(int i=0;i+len<=n;i++)
			{
                if(presum[i+len]-presum[i]==k)//长度为len的子数组的和
				{
                    return len;
                }
            }
        }
        return 0;
    }
}

• 时间复杂度：两层的循环，外层循环遍历$n$，内存循环遍历$n-len$，因此时间复杂度为$O(n^2)$
• 空间复杂度: 借助于一个前缀数组，因此空间复杂度为$O(n)$

本题也可采用哈希表的办法，将当前数组arr[0,i]的和做为关键字，i做为值记录在哈希表hashmap中，循环遍历数组，从开始位置出发，记录前缀数组的和presum，如果这个值不在哈希表中，则将其记录在哈希表中，继续判断presum-k是否在哈希表中，如果也在哈希表中，那么i-hashmap[presum-k]这一数值就可作为累加和为k的数组长度，但不一定是最长的，需要继续进行遍历，直到遍历完成。特别的由于数组中可能存在0，而子数组增加0，数组的和不变，长度会增加，因此初始hashmap[0]=-1，以避免以0开始的子数组的计算。

输入：$[1,-2,1,1,1]$，$0$

初始化$hashmap[0]=-1$，$length$初始化为0

$i$	$presum +=arr[i]$	$hashmap$	$length$
$0$	$1$	$hashmap[1]=0$	$0$
$1$	$1+(-2)=-1$	$hashmap[-1]=1$	$0$
$2$	$-1+1=0$	----------	$max(length,i-hashmap[presum-k])=max(0,3)=3$
$3$	$0+1=1$	----------	$max(length,i-hashmap[presum-k])=max(3,3)=3$
$4$	$1+1=2$	$hashmap[2]=4$	$max(length,i-hashmap[presum-k])=max(3,0)=3$

#
# max length of the subarray sum = k
# @param arr int整型一维数组 the array
# @param k int整型 target
# @return int整型
#
class Solution:
    def maxlenEqualK(self , arr , k ):
        # write code here
        if arr == None&nbs***bsp;len(arr) == 0:
            return 0
        hashmap = {}#构建哈希表
        hashmap[0] = -1#防止数组中有0的情况，数组中增加0，数组的和不变，数组长度+1
        presum = 0
        length = 0
        for i in range(len(arr)):
            presum += arr[i]#构建前缀数组和
            if presum not in hashmap:#哈希表中为存放当前值
                hashmap[presum]=i
            if (presum - k) in hashmap:#presum-k的值在哈希表中，其长度也是最长的，因此可以直接计算总的长度
                length = max(length,i-hashmap[presum-k])

        return length

• 时间复杂度：遍历一次数组，因此时间复杂度为$O(n)$
• 空间复杂度:   借助于一个presum变量以及一个哈希数组，因此空间复杂度为$O(n)$