本文共 1027 字，大约阅读时间需要 3 分钟。

问题描述:一个数组可能包含正数、负数和0.找出和为k的最长子数组的长度。

这种题目有暴力求解方法:

思路:我们考虑以数组中每一个节点作为一个子数组的尾节点，然后对于该节点，从头遍历遍历到该节点位置，遇到第一个和为sum的节点，求出子数组长度...，这种算法其实也需要我们先遍历一遍，算出每个节点到头结点和才行。

最优解法:利用HashMap，时间复杂度仅为O(n),空间复杂度也是O(n)

思路:

1、HashMap的value是节点下标，key是该节点到头结点的数组和。

2、遍历一遍数组，对于某个节点求得的到头结点的sum值，假如HashMap中有一个key等于sum - k,那么就取出value即为该节点的下标，然后相减得到子数组长度。

3、判断该节点的sum值在Map中有没有，如果没有的话，就存下该sum值和下标，如果有的话就别存了，因为对应的不是最长子数组

重点:因为有可能以第一个元素为最长子数组的首节点，所以要最先在Map中存储一个key 为0，value 为-1的元素

代码如下

package Array;import java.util.HashMap;public class LongestSubArrayEqualsSum2 {    public static int longestSubArrayEqualsSum2(int[] array,int k){        HashMap
   
     map = new HashMap<>();        int len = 0;//和为k的最长子数组长度        int sum = 0;        map.put(0,-1);        for(int i = 0; i < array.length; i++){            sum += array[i];            if(map.containsKey(sum - k)){                len = len > map.get(sum - k)?len:map.get(sum - k);            }            if(!map.containsKey(sum)){                map.put(sum,i);            }        }        return len;    }}
   

转载地址：http://sizji.baihongyu.com/