子数组和的一系列问题（上）

LeetCode解题思路及一些问题延伸

作者 Trevor Cui 日期 2018-01-20
LeetCode Array
子数组和的一系列问题（上）

Algorithm 专题将会是我刷算法题的一些总结。对于数组类型的算法题来说，有关于子数组和的一系列问题，思路都比较类似。接下来，让我们从子数组最大累加和开始吧！

子数组最大累加和

题目简析

本题来源于LeetCode 53题 Maximum Subarray。

给定一个数组，数组内的数字有正有零有负，求数组内累加和最大的子数组。（无论是求和的值、求子数组长度、求子数组起始点都一样，无非是记录的值不一样罢了）

解题思路

子数组相关的问题都可以用两个 for 循环去遍历子数组的起始位置和结束位置，那么总归会遍历到那个最大累加和的子数组，从而记录并输出出来。

显而易见，这种做法的算法复杂度是O(n^2)。

但是这道题有一个思路很简单，但不是很容易自然想到的解法。用一个current值记录当前的子数组和。一旦值小于0，则置为0。同时用一个变量记录最大的current值。该解法虽然不容易自然想到，但很容易想到其思路的正确性：设一个数组的最大和子数组起始坐标为i，那么以i开头的子数组中若存在和小于0的，去掉这部分，显然剩下的子数组和更大。

该做法时间复杂度O(n),空间复杂度O(1)。

参考代码

int maxSubArray(vector<int>& nums) {
    // 考虑空数组异常
    if(nums.size() == 0) return 0;
    
    // 这样写可以避免数组内都是负数的情况，max会保存最大的负数
    int max = nums[0];
    
    int cur = 0;
    for(int i = 0; i < nums.size(); i++) {
        cur += nums[i];
        if(max < cur) max = cur;
        if(cur < 0) cur = 0;
    }
    return max;
}

累加和为给定值 k 的子数组

题目简析

这类型有三种题，一个是来源于LeetCode 560题 Subarray Sum Equals K。该题为求累加和为给定值的子数组的数量。另一种为求子数组的最大长度。

第三种相对较简单，在第二种题的基础上增加限定条件：所给数组元素均为非负数（或都是正数）。

解题思路

子数组和相关的问题如果想通过一次遍历就能得到结果，思路都可以往累加和的差上去考虑。比如a[i] 到 a[j] 的累加和，等于 a[0] 到 a[j] 的累加和减去 a[0] 到 a[i-1] 的累加和。因此，若把累加和记做一个数组，也许就能想到用空间换取时间的算法。

前两种题做法相差不大。都是利用哈希表对已计算的累加和进行存储。首先我们可以很容易想到的是，当得到当前 i 位置的累加和 sum 时，若 sum - k 在累加和数组之前存在，那么就存在以 i 结尾的累加和为 k 的数组。而哈希表可以把遍历累加和数组的过程变成 O(1) 的时间复杂度。

对于统计子数组数量来说，哈希表存放的是当前累加和出现过的次数。而对于求最长子数组来说，哈希表存放的是当前累加和最早出现的位置。

哈希表的解法时间复杂度 O(n)，空间复杂度 O(n)。

对于第三题来说，由于有了非负数（或正数）的限定条件，left、right 两指针的思路很清晰：当前和小于等于 k，右指针向右移动，同时加上右指针的值；若大于，则左指针向右，同时减去左指针的值。同时，记录等于 k 时的最长长度。该解法时间复杂度 O(n)，空间复杂度 O(1)。

参考代码

前两题：

int subarraySum(vector<int>& nums, int k) {
    // 始终记得处理空数组
    if(nums.size() == 0) return 0;
    
    map<int,int> sumMap;
    
    // 对于初始时数组和为0的处理（很重要！）：
    // 第一题，先记录0出现了1次
    sumMap[0] = 1;
    // 第二题，先记录0出现在-1的位置上
    // sumMap[0] = -1;
    
    int sum = 0;     // 当前数组和
    int count = 0;
    for(int i = 0; i < nums.size(); i++) {
        sum += nums[i];
        if(sumMap.find(sum - k) != sumMap.end())  // 若 sum - k 已存在
            count += sumMap[sum - k];
            // count = max(count, i - sumMap[sum - k])
            
        // 在哈希表中记录sum
        if(sumMap.find(sum) == sumMap.end())
            sumMap[sum] = 1;
            // sumMap[sum] = i;
        else
            sumMap[sum]++;
            // 对于第二题，若 sum 已经出现过，不做任何处理
    }
    return count;
}

第三题：

int getMaxLength(vector<int>& nums, int k) {
    if(nums.size() == 0 || k < 0) return 0;
    int left = 0, right = 0;
    int sum = 0;
    int res = 0;
    while(right < nums.size()) {
        if(sum == k) {
            res = max(res, right - left);
            sum += nums[right++];
        }
        else if(sum < k) {
            sum += nums[right++];
        }
        else if(sum > k) {
            sum -= nums[left--];
        }
    }
    return res;
}

补充题目

1、给定一个数组，求所有子数组中正数与负数个数相等的最长子数组长度。

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

理解了前面的原题解法后，这两道补充题思路很简单，第一题把所有正数变成 1，所有负数变成 -1，即所求为新数组中和为 0 的最长子数组。第二题几位 1 不变，0 变成 -1 后的新数组中和为 0 的最长子数组。

累加小于等于给定值 k 的子数组

题目简析

给定一个数组，数组内的数字有正有零有负，求数组内累加小于等于 k 的最长子数组长度。

解题思路

该题看起来跟累加和等于 k 的题目差不多，但实际上比上一题要难不少。主要难点在于哈希表无法存储大于或等于某一个值的累加和最早出现的位置。为了在小于 O(n) 的时间复杂度内找到该位置，我们采用一个辅助数组来存储最大的累加和。这样一来，得到的辅助数组是有序的，故可以通过二分查找找到大于或等于某一个值的累加和最早出现的位置。思路还是比较清晰的，所以还是看代码为主吧。

该做法时间复杂度O(nlogn),空间复杂度O(1)。

参考代码

int maxLenth(vector<int>& nums, int k) {
    if(nums.size() == 0) return 0;
    vector<int> maxSum;
    int sum = nums[0];
    int pre = nums[0];
    int res = 0;
    maxSum.push_back(pre);
    for(int i = 1; i < nums.size(); i++) {
        sum += nums[i];
        pre = max(pre, sum);
        maxSum.push_back(pre);
        int index = getIndex(maxSum, sum - k)
        res = max((index == -1) ? 0 : (i - index + 1), res);
    }
    return res;
}

int getIndex(vector<int>& nums, int k) {
    int low = 0;
    int high = nums.size() - 1;
    int mid = 0;
    int res = -1;
    while(low <= high) {
        mid = (low + high) / 2;
        if(nums[mid] >= k) {
            res = mid;
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    return res;
}
FEATURED TAGS
LeetCode Array