求数组中和为K的子数组数量：分治法实现及问题求助

问题需求 #

需要实现一个函数，统计数组中和为K的连续子数组数量，要求时间复杂度为O(n log n)，且用分治法实现。现有两段代码均无法正确解决问题，请求修正。

第一段分治法代码的问题 #

原代码如下：

int division(int *num, int low, int high, int k, int n, int count) {
    if (low == high)
        return num[low];
    int mid = (low + high) / 2;
    int lsum = division(num, low, mid, k, n, count);
    int rsum = division(num, mid + 1, high, k, n, count);
     
    if (lsum == k)
        count++;
    if (rsum == k)
        count++;
    if ((lsum + rsum) == k)
        count++;
    return count;
}

这段代码存在核心逻辑错误：

1. 递归返回值设计错误：函数返回子数组的和而非符合条件的子数组数量，导致上层递归无法正确统计结果。
2. 统计范围严重缺失：仅考虑左右子数组整体的和等于K、以及左右整体相加等于K的情况，完全忽略了左右内部的所有可能子数组，也未覆盖跨越中间点的连续子数组。
3. 参数传递错误：count是传值调用，修改后不会影响上层递归的计数，最终返回结果无意义。

第二段记忆化递归代码的问题 #

原代码（葡萄牙语变量注释：lembrar=记录，valor=目标值，acumulo=计数器）如下：

int soma(int valor,int*numeros,int tamanho,int* lembrar){
    
    if(valor==0)
        return 1;
    if(valor<0)
        return 0;
    if(lembrar[valor] != -1)
        return lembrar[valor];
        
    int acumulo=0;
    for(int i=0;i<tamanho;i++)
    {
    
        int target = valor - numeros[i];
        int result = soma(target,numeros,tamanho,lembrar);
        acumulo += result;
        lembrar[target] = result;
    }
    
    lembrar[valor] = acumulo;
    return acumulo;
}

这段代码的核心问题是方向错误：它实现的是子集和计数（允许选取任意不连续元素），而非题目要求的连续子数组计数。此外，即使忽略这一点，它也无法正确处理零值：允许重复选取元素的逻辑会导致零值引发无限递归或重复计数，完全不符合子数组的连续特性。

正确的分治法实现 #

核心思路 #

分治法将数组拆分为左右两部分，统计三类符合条件的子数组：

1. 完全位于左半部分的子数组
2. 完全位于右半部分的子数组
3. 跨越中间点的连续子数组

对于第三类跨中间的子数组，通过前缀和+排序二分的方式统计：

• 计算左半部分从中间点向左的所有前缀和（包含空前缀，和为0）
• 计算右半部分从中间点向右的所有前缀和（包含空前缀，和为0）
• 对右前缀和数组排序，遍历左前缀和，用二分查找统计右前缀和中等于K - 左前缀和的数量，两者相加即为跨中间的符合条件的子数组数量。

完整代码实现 #

#include <stdio.h>
#include <stdlib.h>

// 归并排序：用于对前缀和数组排序，支持二分查找
void merge(long long arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    long long *L = (long long*)malloc(n1 * sizeof(long long));
    long long *R = (long long*)malloc(n2 * sizeof(long long));
    
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    }
    
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    
    free(L);
    free(R);
}

// 二分查找：统计数组中等于target的元素个数
int count_target(long long arr[], int left, int right, long long target) {
    int first = -1, last = -1;
    // 找第一个匹配的位置
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            first = mid;
            right = mid - 1;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (first == -1) return 0;
    // 找最后一个匹配的位置
    left = first;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            last = mid;
            left = mid + 1;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return last - first + 1;
}

// 统计跨越中间点的符合条件的子数组数量
int count_cross(int *num, int low, int mid, int high, int k) {
    int left_len = mid - low + 2;
    int right_len = high - mid + 1;
    long long *left_prefix = (long long*)malloc(left_len * sizeof(long long));
    long long *right_prefix = (long long*)malloc(right_len * sizeof(long long));
    
    // 左半部分：从mid向左累加前缀和（包含空前缀，和为0）
    left_prefix[0] = 0;
    long long sum = 0;
    for (int i = mid; i >= low; i--) {
        sum += num[i];
        left_prefix[mid - i + 1] = sum;
    }
    
    // 右半部分：从mid+1向右累加前缀和（包含空前缀，和为0）
    right_prefix[0] = 0;
    sum = 0;
    for (int i = mid + 1; i <= high; i++) {
        sum += num[i];
        right_prefix[i - (mid + 1) + 1] = sum;
    }
    
    // 对右前缀和排序，以便二分查找
    merge(right_prefix, 0, (right_len - 1) / 2, right_len - 1);
    
    int count = 0;
    // 遍历左前缀和，找匹配的右前缀和数量
    for (int i = 0; i < left_len; i++) {
        long long target = k - left_prefix[i];
        count += count_target(right_prefix, 0, right_len - 1, target);
    }
    
    free(left_prefix);
    free(right_prefix);
    return count;
}

// 分治主函数
int division(int *num, int low, int high, int k) {
    if (low > high) return 0;
    if (low == high) {
        return (num[low] == k) ? 1 : 0;
    }
    
    int mid = (low + high) / 2;
    int left_count = division(num, low, mid, k);
    int right_count = division(num, mid + 1, high, k);
    int cross_count = count_cross(num, low, mid, high, k);
    
    return left_count + right_count + cross_count;
}

// 对外调用接口
int subarraySum(int* nums, int numsSize, int k) {
    return division(nums, 0, numsSize - 1, k);
}

// 测试示例
int main() {
    int nums[] = {0, 0, 0};
    int k = 0;
    printf("%d\n", subarraySum(nums, 3, k)); // 预期输出：6（所有可能的连续子数组）
    return 0;
}

关键说明 #

1. 使用long long存储前缀和：避免数组元素累加时出现整数溢出问题。
2. 归并排序+二分查找：保证跨中间部分的统计时间复杂度为O(n log n)，整体分治法的时间复杂度符合要求。
3. 空前缀的处理：空前缀（和为0）用于统计从中间点开始的子数组（比如右半部分中直接和为K的子数组）。

内容的提问来源于stack exchange，提问作者Dalton Gomes