如何使用之前递归调用的变量？

Question

一般问题： 给定一个整数数组 nums 和一个整数 k。如果连续子数组中有 k 个奇数，则称它为 nice。 Returnnice子数组的个数。

我的问题： 我想递归地解决这个问题。我正在努力实现的部分是如何使用以前的每个递归调用中的 count 并总结所有计数，以及 return 最后一个 count 就像它在尝试。

示例：

Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

我的尝试：

int helperFunction(vector<int> &nums, int k, int starter, int count)
{
    int sum=0;
    if (starter >= nums.size())
    {
        return count;
    }
    for (int i = starter; i < nums.size(); i++)
    {
        if (nums[i] % 2 == 1)
        {
            if (++sum == k)
            {
                count += nums.size() - i;
                sum = 0;
            }
        }
    }
    return helperFunction(nums, k, starter + 1, count);
}
int numberOfSubarrays(vector<int> &nums, int k)
{
    return helperFunction(nums, k, 0, 0);
}

int main()
{
    vector<int> mine;
    int myints[] = {1, 1, 2, 1, 1};

    mine.assign(myints, myints + 5);
    cout << "Output : " << numberOfSubarrays(mine, 3);
    return 0;
}

Return 值：

这次实际尝试的return值为0，说明程序至少在语法上没有错误。

Answer 1

它不是特别适合递归。可能只需在数组上传递一次即可解决。

也就是说，对您的代码稍作调整就可以使其正常工作。没有理由将计数传递给递归方法。

您的方法计算 'nice' 以给定索引开头的子数组的数量。将其添加到从下一个索引开始的数字，然后 return 它。

int helperFunction(vector<int> &nums, int k, int starter)
{
    int sum=0, count=0;
    if (starter >= nums.size())
    {
        return 0;
    }
    for (int i = starter; i < nums.size() && sum <= k; i++)
    {
        if (nums[i] % 2 == 1)
        {
            sum++;
        }
        if (sum == k)
        {
            count++;
        }        
    }
    return helperFunction(nums, k, starter + 1) + count;
}

我不确定你的计数是否正确。这可以优化很多，但这应该证明递归方法。

如何使用之前递归调用的变量？

How can I use a variable from a previous recursive call?

c++

recursion