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

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

补充问题：

1、给定一个无序数组arr，其中元素可正、可负、可 0。求arr所有子数组中正数与负数个数相同的最长子数组长度。

2、给定一个无序数组arr，其中元素只是 1 或 0。求arr所有的子数组中 0 和 1 个数相等的最长数组长度。

基本思路：

　　原问题。使用一个哈希表map，记录每一个累加和情况出现的位置，相同的累加和只记录出现最早的位置。

　　从左到右遍历数组，假设遍历到位置 i，记录 arr[0…i] 的累加和 sum，如果该累加和不存在于map中，将该 sum 作为 key， i 作为 value 添加到map中；否则不进行添加。接下来判断 sum - k 这个累加和是否存在与map中，如果存在的话，假设位置记为 index，那么可想而知，i - index 其实就是一个累加和为k的子数组长度。使用一个全局变量保存遍历到的最长子数组长度。继续遍历数组按照上述方法寻找其他的累加和为k的子数组。

　　这里我们试着考虑一个情况，假设我们遍历到位置 i，发现此时累加和为k，很显然，这满足题意，arr[0…i] 就是一个累加和为 k 的子数组，但是我们发现，如果我们按照上述方法在map中寻找 sum - k 的元素，也就是 0，map 中是不会有 0 这个元素的，所以最终这个子数组会被忽略。所以在这里强调很重要的一点：map初始的时候必须要添加一个key = 0、value = -1 的键值对，这样可以避免以位置 0 开头的子数组的丢失。
 

def maxLength(L,k):if L == None or len(L) == 0:return 0map_ = {}map_[0] = -1sum_ = 0length = 0for i in range(len(L)):sum_ += L[i]if (sum_ - k) in map_:length = max(length,i-map_[sum_-k])else:map_[sum_] = ireturn length

 

总结

以上是生活随笔为你收集整理的未排序数组中累加和为给定值的最长子数组系列问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。