除了求最大子段和用的 O(n)动态规划，求其他满足“某种条件"的子段和可用”前缀和“解法。runningSum 对应“前缀和”数组的“后闭”模式。runningSum 可以认为是滑动窗口的特例。

和为 target 的子段数

  • https://leetcode.com/problems/binary-subarrays-with-sum/
  • https://leetcode.com/problems/subarray-sum-equals-k/
  • https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/
int numSubarraysWithSum(vector<int>& A, int target) {
    unordered_map<int, int> presum = {{0,1}}; // sum=>count
    int runningSum = 0;

    int ans = 0;
    for (int a : A) {
        runningSum += a;
        // 需S=runningSum-toFind
        int toFind = runningSum - target;
        if (presum.count(toFind)) ans += presum[toFind];
        presum[runningSum]++;
    }
    return ans;
}

和为 target 的不重叠子段数

  • https://leetcode.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/
int maxNonOverlapping(vector<int>& nums, int target) {
    const int N = nums.size();
    // 判断重叠，使用sum=>idx、记录lastIdx
    unordered_map<int, int> presum = {{0, -1}}; // sum=>idx
    int runningSum = 0, lastIdx = -1, ans = 0;
    for (int i = 0; i < N; i++) {
        runningSum += nums[i];
        // runningSum-toFind=target
        int toFind = runningSum - target;
        if (presum.count(toFind)) {
            // 保证不重叠，presum相关是前开后闭区间
            if (presum[toFind] >= lastIdx) {
                ans++;
                lastIdx = i;
            }
        }
        // 多个相同值保留最右的，因为前面的已处理过
        presum[runningSum] = i;
    }
    return ans;
}

最接近 target 的子段和

假设已把前面各累加和放到的 set 中，对当前 runningSum 要在 set 中找 toFind 使：runningSum-toFind 最接近 target，即找最接近 runningSum-target 的旧和值 toFind。设 x=runningSum-target，看备选 it=lower_bound(x)和 prev(it)哪个更接近 x。

java 代码可参考，jave 中 TreeSet 对应 c++的 std::set

落在范围[lower,upper]的子段和有多少

用 map 记录各累加和出现的次数。对当前 runningSum 要在 map 中查找 toFind 使 lower<=runningSum-toFind<=upper，runningSum-upper<=toFind<=runningSum-lower。

int countRangeSum(vector<int>& nums, int lower, int upper) {
    map<long, int> cnt = {{0, 1}} // sum=>count
    long runningSum = 0;

    int ans = 0;
    for (int num : nums) {
        runningSum += num;
        // 找数x使lower<= runningSum-x <=upper，runningSum-upper<= x <=runningSum-lower
        auto it1 = cnt.lower_bound(runningSum - upper);
        auto it2 = cnt.upper_bound(runningSum - lower);
        for (auto it = it1; it != it2; it++) {
            ans += it->second;
        }
        cnt[runningSum]++;
    }
    return ans;
}

可被 k 整除的子段和有多少

int subarraysDivByK(vector<int>& A, int K) {
    unordered_map<int, int> cnt = {{0, 1}}; // sum=>count
    int runningSum = 0;

    int ans = 0;
    for (int a : A) {
        runningSum = (runningSum + a % K + K) % K; // a可能为负
        // (runningSum-toFind)%K==0，(toFind==runningSum)%K
        ans += cnt[runningSum];
        cnt[runningSum]++;
    }
    return ans;
}

子段和等于 k 的倍数、且子段长>=2

bool checkSubarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> mp = {{0, -1}}; // sum=>idx
    int runningSum = 0;
    // 子段和是k的倍数，即子段和(runningSum-toFind)%k==0
    // (toFind==runningSum)%K
    // 为让子段尽量长，多个相同runningSum的只保留第一个
    for (int i = 0; i < nums.size(); i++) {
        runningSum += nums[i];
        if (k) runningSum %= k;
        if (!mp.count(runningSum)) {
            mp[runningSum] = i;
        } else if (i - mp[runningSum] >= 2) {
            return true;
        }
    }
    return false;
}

子段在重排和替换 k 个字符后，能够成回文串吗

vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
    // "前缀和"preOdds[i+1]对应s[0..i]，各个位对应各字符的奇偶性
    vector<int> preOdds = {0};
    int runningOdds = 0;
    for (char c : s) {
        runningOdds ^= 1 << (c - 'a');
        preOdds.push_back(runningOdds);
    }

    vector<bool> ans;
    for (auto &query : queries) {
        // 回文需要oddCnt/2<=k
        int odds = preOdds[query[1] + 1] ^ preOdds[query[0]];
        int oddCnt = bitset<26>(odds).count();
        ans.push_back(oddCnt / 2 <= query[2]);
    }
    return ans;
}

两个不重叠子段的最大和

  • https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/
int maxSumTwoNoOverlap(vector<int>& A, int l1, int l2) {
	// 题目：两个不重叠子段，l1在l2前、或l2在l1前
	const int N = A.size();
	vector<int> presum(N + 1, 0);
	for (int i = 0; i < N; i++) {
		presum[i + 1] = presum[i] + A[i];
	}

	int l1max = 0, l2max = 0, ans = 0;
	for (int i = l1 + l2; i <= N; i++) {
		// l1在l2前
		l1max = max(l1max, presum[i - l2] - presum[i - l1 - l2]);
		ans = max(ans, l1max + (presum[i] - presum[i - l2]));
		// l2在l1前
		l2max = max(l2max, presum[i - l1] - presum[i - l1 - l2]);
		ans = max(ans, l2max + (presum[i] - presum[i - l1]));
	}
	return ans;
}