脚本宝典收集整理的这篇文章主要介绍了未排序正数数组中累加和为给定值的最长子数组的长度 & 未排序数组中累加和为给定值的最长子数组系列问题 & 在二叉树中找到累加和为指定值的最长路径长度，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

未排序正数数组中累加和为给定值的最长子数组的长度

题目：未排序正数数组中累加和为给定值的最长子数组的长度

《程序员代码面试指南》第124题 P382 难度：尉★★☆☆

本题很简单，最优解可以做到@R_415_1304@为O(N)，额外空间复杂度为O(1)。

核心在于使用2个位置/指针——left和right来标记子数组的左右两头。

初始时left和right都为0，sum表示arr[left..right]的和。

通过sum与给定值k的比较结果来决定left移动还是right移动。具体细节不再赘述，详见代码：

public int getMaxLength(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k <= 0) {
        return 0;
    }
    int left = 0;
    int right = 0;
    int sum = arr[0];
    int len = 0;
    while (right < arr.length) {
        if (sum == k) {
            len = Math.max(len, right - left + 1);
            sum -= arr[left++];
        } else if (sum < k) {
            right++;
            if (right == arr.length) {
                break;
            }
            sum += arr[right];
        } else {
            sum -= arr[left++];
        }
    }
    return len;
}

注意left、right的移动与加减值的顺序。left是先减值后加1，right是先加1后加值。否则会出现一些问题。总之要保证left和right代表的就是当前子数组的最左和最右的索引位置。（我一开始让right先加值后加1，结果right代表的是子数组最右端+1的位置。当加上原数组最大索引位置的值后，right加1后直接等于数组长度，直接满足退出循环的条件了。这是不对的，这个时候还需要做判断sum大于或等于k，来移动left。直到此时sum已经小于k了，需要再让right加1，并且right已经是最右端的情况下，才能退出循环）。

未排序数组中累加和为给定值的最长子数组系列问题

题目：未排序数组中累加和为给定值的最长子数组长度

《程序员代码面试指南》第125题 P384 难度：尉★★☆☆

本题去掉了上题中正数的条件。本题中数组元素可正可负可0。

另外，还有2个补充问题：①.求正数与负数个数相等的最长子数组长度 ②.求0和1个数相等的最长子数组长度

其实这2个补充问题就可以转化为求未排序数组中累加和为给定值的最长子数组的长度这个问题。

只要让①中正数都变成1，负数都变成-1；让②中0都变成-1即可。此时就转化为了求未排序数组中累加和为0的最长子数组的长度。

本题思路略为复杂。我自己的方法用了双重循环，达不到最优解时间复杂度O(N)，额外空间复杂度O(N)的要求。

本题的核心在于：s(i)代表子数组arr[0..i]的和，arr[j..i]则为s(i)-s(j-1)。

只通过一次循环解决该问题。在遍历的过程中，将最早出现的累加和的值加入map中。key为累加和的值，value为最早出现的位置索引。

遍历到i位置时，计算sum=s(i)，并且从map中找key为sum-k的键值对。如果没有，则证明之前没有出现过累加和为sum-k的子数组。如果有，则因为它记录了最早出现的索引位置，所以这2个索引之间的子数组即为以i索引为右端的累加和为k的最长子数组(sum-(sum-k)=k)。然后与已有的len之间取最大值。

不过需要额外注意，在遍历之前需要首先将(0,-1)这个键值对加入map中，代表了如果任何一个数都不加的时候，累加和为0。这样，从0位置开始的子数组也被我们考虑到了

详细算法步骤与原因解释见书P384-385。这里贴出标答代码：

public int maxLength(int[] arr, int k) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    map.put(0, -1); // important
    int len = 0;
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
        if (map.containsKey(sum - k)) {
            len = Math.max(i - map.get(sum - k), len);
        }
        if (!map.containsKey(sum)) {
            map.put(sum, i);
        }
    }
    return len;
}

脚本宝典总结

以上是脚本宝典为你收集整理的未排序正数数组中累加和为给定值的最长子数组的长度 & 未排序数组中累加和为给定值的最长子数组系列问题 & 在二叉树中找到累加和为指定值的最长路径长度全部内容，希望文章能够帮你解决未排序正数数组中累加和为给定值的最长子数组的长度 & 未排序数组中累加和为给定值的最长子数组系列问题 & 在二叉树中找到累加和为指定值的最长路径长度所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。