和为k的最长子数组及其延伸

问题1：

/**
 * 问题描述：
 * 给定一个无序数组arr，其中元素可正、可负、可0，
 * 求arr所有的子数组中正数与负数个数相等的最长子数组长度
 *
 * 解题思路：对数组进行处理，正数为1，负数为-1，求和是0的最长子数组长度
 */

问题2：

/**
 * 问题描述：
 * 给定一个无序数组arr，其中元素只是1或0，
 * 求arr所有的子数组中0和1个数相等的最长子数组长度。
 *
 * 解题思路：对数组进行处理，将0变为-1，求和是0的最长子数组长度
 */

问题1、2都可以归结到一个问题：

给定一个无序数组arr，其中元素可正、可负、可0，再给定一个整数k。

求arr所有的子数组中累加和为k的最长子数组长度

代码如下：

/** @brief
 * 给定一个无序数组arr，其中元素可正、可负、可0，再给定一个整数k
 * 求arr所有的子数组中累加和为k的最长子数组长度
 *
 * @param arr[] int
 * @param length int -数组长度
 * @param k int -累加和为k
 * @return int
 *
 */
int longestSubArrayLength(int arr[], int length, int k)
{
    hash_map<int, int> sumIdxMap;
    sumIdxMap.insert(make_pair(0, -1));

    int sum = 0;
    int ret = 0;
    for(int i = 0; i < length; ++i)
    {
        sum += arr[i];
        if(sumIdxMap.find(sum - k) != sumIdxMap.end())
        {
            ret = max(ret, i - sumIdxMap[sum - k]);
        }

        if(sumIdxMap.find(sum) != sumIdxMap.end())
        {
            sumIdxMap.insert(make_pair(sum, i));
        }
    }

    return ret;
}

说明：为了将算法的时间复杂度限定到O(n)，这里使用了C++下的hash_map(map是基于红黑树的，存取复杂度是O(logn))，其存取的时间复杂度均是O(1)。

由于hash_map是非STL中的容器，所以需要添加相应的头文件及命名空间。

/**
 * Linux下
 */
#include <hash_map>
using namespace __gnu_cxx;

windows直接添加头文件即可使用。

原文链接: https://www.cnblogs.com/fengkang1008/p/4864032.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍