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

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)$

#
# 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)$