C++程序寻找给定和的子数组-第1集（非负数）

在编程过程中，找到一个数组内满足总和为给定值的子数组是一件比较常见的事情。今天，我们将学习如何用C++编写一个程序，来寻找一个非负整数数组中满足给定值的子数组。

问题描述

给定一个非负整数数组和一个目标值，需要找到该数组中所有满足总和等于目标值的子数组。

例如，如果给定数组是{2, 3, 5, 7, 8}，目标值为10，那么满足条件的子数组有{2, 3, 5}和{8}，因为它们的总和都是10。

解决方案

在这里，我们将学习两种方法来解决这个问题，一种是暴力枚举，另一种是使用前缀和。

方法1：暴力枚举

暴力枚举的思路非常简单。我们可以先从数组的第一个元素开始，向后遍历数组所有可能的子数组。对于每个子数组，我们都计算它们的总和并检查是否等于目标值。

代码实现：

#include <iostream>
#include <vector>
using namespace std;

// 查找所有满足总和为sum的子数组
vector<vector<int>> findSubarray(vector<int> nums, int sum) {
    vector<vector<int>> res;    // 存储结果
    int n = nums.size();

    // 枚举所有可能的子数组
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int sum_sub = 0;    // 当前子数组的总和
            vector<int> sub;    // 当前子数组

            // 计算子数组的总和
            for (int k = i; k <= j; k++) {
                sum_sub += nums[k];
                sub.push_back(nums[k]);
            }

            // 当子数组的总和等于给定的sum时，将其加入到结果中
            if (sum_sub == sum) {
                res.push_back(sub);
            }
        }
    }

    return res;
}

int main() {
    vector<int> nums = {2, 3, 5, 7, 8};
    int sum = 10;

    vector<vector<int>> ans = findSubarray(nums, sum);

    // 输出结果
    for (auto sub : ans) {
        for (auto num : sub) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

运行结果：

2 3 5 
8

以上就是暴力枚举的方法，它的时间复杂度为 $O(n^3)$ ，时间效率非常低。

方法2：前缀和

前缀和是一种常见的算法，用于快速计算数组的区间和。它的思路是先用一个数组 $sum$ 存储原数组中每个位置之前元素的和，即 $sum[i] = nums[0] + nums[1] + \dots + nums[i]$ 。然后，我们可以通过计算 $sum[j] - sum[i-1]$ ，在 $O(1)$ 的时间内计算出原数组的任意一个子数组的和。

由于数组的元素均为非负整数，因此我们可以在计算前缀和时，一旦发现某个前缀和大于目标值，就直接跳出循环。这样可以大大提高程序的效率。

代码实现：

#include <iostream>
#include <vector>
using namespace std;

// 查找所有满足总和为sum的子数组
vector<vector<int>> findSubarray(vector<int> nums, int sum) {
    vector<vector<int>> res;    // 存储结果
    int n = nums.size();
    vector<int> preSum(n+1, 0); // 前缀和数组
    for (int i = 1; i <= n; i++) {
        preSum[i] = preSum[i-1] + nums[i-1]; // 计算前缀和
    }

    // 枚举所有可能的子数组
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j <= n; j++) {
            // 如果某个前缀和大于目标值，直接跳出内层循环
            if (preSum[j] - preSum[i] > sum) {
                break;
            }
            // 如果当前子数组的总和等于给定的sum，将其加入到结果中
            if (preSum[j] - preSum[i] == sum) {
                vector<int> sub(nums.begin()+i, nums.begin()+j);
                res.push_back(sub);
            }
        }
    }

    return res;
}

int main() {
    vector<int> nums = {2, 3, 5, 7, 8};
    int sum = 10;

    vector<vector<int>> ans = findSubarray(nums, sum);

    // 输出结果
    for (auto sub : ans) {
        for (auto num : sub) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

运行结果：