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

题意整理

• 给定一个未排序数组。
• 求累加和为k的子数组中最长的那个子数组的长度。

方法一（枚举）

1.解题思路

• 首先构建前缀和数组， 表示原数组索引0到i-1之间所有元素之和。
• 然后按子数组可能的长度，进行逆序枚举。
• 当某个长度下，子数组累加和刚好等于k，则直接返回。

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];
        }

        //逆序遍历所有可能的长度
        for(int len=n;len>=1;len--){
            for(int i=0;i+len<=n;i++){
                //如果某个子数组累加和为k，则直接返回len
                if(presum[i+len]-presum[i]==k){
                    return len;
                }
            }
        }
        return 0;
    }
}

3.复杂度分析

• 时间复杂度：循环的次数为 ，当时，这个数的值最大为 ，所以时间复杂度为 。
• 空间复杂度：需要长度为n+1的前缀和数组，所以空间复杂度为 。

方法二（哈希表）

1.解题思路

• 分析：由于前缀和数组与索引有一个对应关系，而子数组累加和等于两个索引对应前缀和之差，问题转化为在前缀和数组中寻找差为固定值的两个索引（在数组中寻找两数之差）。
• 基本思路：可以借助哈希表，存储对应的前缀和，由于要找最长子数组，所以遇到重复的前缀和，保持前缀和key对应的索引value不变。当发现哈希表里存在sum-k的键时，即说明存在累加和为k的子数组，记录长度，并与res比较取较大者。

动图展示：

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 res=0;
        //构建哈希表
        Map<Integer,Integer> map=new HashMap<>();
        //记录前缀和
        int sum=0;
        //定义一个虚索引-1，将{0，-1}添加到map
        map.put(0,-1);
        for(int i=0;i<n;i++){
            sum+=arr[i];
            //如果map包含sum-k,将sum-k对应索引记为j,则j+1到i之间的子数组和为k
            if(map.containsKey(sum-k)){
                res=Math.max(res,i-map.get(sum-k));
            }
            //如果不包含sum，则将{sum,i}添加到map，否则保持值不变
            map.put(sum,map.getOrDefault(sum,i));
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：只需要遍历一次arr数组，所以时间复杂度为 。
• 空间复杂度：需要额外最多长度为n的哈希表存储前缀和，所以空间复杂度为 。