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

发表于 | 浏览 次

原题

给定一个无序数组,其中元素可正,可负,可0.给定一个整数k,求arr所有的子数组中累加和为k的最长子数组长度.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maxLength(vector<int> &arr, int k) {
    if (arr.empty()) {
        return 0;
    }
    map<int, int> mp;
    mp[0] = -1;
    int len = 0;
    int sum = 0;
    for (int i = 0; i < arr.size(); i++) {
        sum += arr[i];
        if (mp.find(sum - k) != mp.end()) {
            len = max(len, i - mp[sum - k]);
        }
        if (mp.find(sum) == mp.end()) {
            mp[sum] = i;
        }
    }
    return len;
}

补充题1

补充题2

类似题

138. 子数组之和

给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置

样例

样例 1:

1
2
3
输入: [-3, 1, 2, -3, 4]
输出: [0,2] 或 [1,3]	
样例解释： 返回任意一段和为0的区间即可。

样例 2:

1
2
输入: [-3, 1, -4, 2, -3, 4]
输出: [1,5]

样例 3:

1
2
输入: [3,4,5,6,-3,-4,-5,-6]
输出: [0,7]

样例 4:

1
2
输入: [1,0,-1]
输出: [1,1]

注意事项: 至少有一个子数组的和为 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    vector<int> subarraySum(vector<int> &nums) {
        // write your code here
        if(nums.empty()){
            return {};
        }
        int sum = 0;
        vector<int> res;
        map<int, int> mp;
        for(int i=0;i<nums.size();++i){
            sum += nums[i];
            if(sum == 0){
                res.push_back(0);
                res.push_back(i);
                return res;
            }
            if(mp.find(sum)!=mp.end()){
                res.push_back(mp[sum]+1);
                res.push_back(i);
                return res;   
            }
            mp[sum] = i;
        }
        
        return res;
    }
};

此题与上题的相似之处在于:需要用到相同的结论:
s[i]= arr[0] + arr[1] +…+arr[i]
s[j]= arr[0] + arr[1] +…+arr[j]
假设i > j,则
s[i] - s[j] = arr[j+1] + arr[j+2] + … + arr[i]

复杂度分析

理论上, 时间复杂度为O(n).但实际实现时,时间复杂度为O(nlogn).因为map的find方法查找一个数的时间复杂度为O(logn)
空间复杂度为O(n)

题目来源: leetcode

560. Subarray Sum Equals K

930 binary subarrays with sum

另有使用三指针的解法,可以尝试看看试用否,三指针解法时间复杂度为O(n),空间复杂度为O(1),是最优解法