时间戳

首页 > 解决方案 > 我不明白如何使用嵌套循环计算每个可能子数组的总和

c++ - 我不明白如何使用嵌套循环计算每个可能子数组的总和

问题描述

作业问的问题是：

编写一个函数 secondSmallestSum ，当传递一个长度大于 1 的 int 数组时，将计算每个可能子数组的元素之和，然后返回找到的第二小的和。最小和次小的总和可能具有相同的值。

子数组是数组中元素的连续范围。例如，如果您有一个长度为 4 的数组 {1,2,3,4}，那么完整的子数组集是：

{1}，{1,2}，{1,2,3}，{1,2,3,4}，{2}，{2,3}，{2,3,4}，{3}， {3,4}、{4}

那么每个子数组的总和是：

1, 3, 6, 10, 2, 5, 9, 3, 7, 4

此问题的主函数必须调用您的 readNumbers 函数，然后将新数组传递给您的 secondSmallestSum 函数，显示找到的第二小的总和，最后删除该数组。

到目前为止，我的代码会打印用户输入的数字。

#include <iostream>

int *readNumbers(int n)
{
    int *a = new int[n];
    for (int i = 0; i < n; i++){
        std::cin >> a[i];
    }
    return a;
}

int main()
{
    int length = 5;
    int *ptr = readNumbers(length);
    printNumbers(ptr, length);
    return 0;
}

我希望这个数组（示例）{4,0,9} 输出 {4}、{4,0}、{4,0,9}、{0}、{0,9} 和{9}。每个数组的总和将输出为：4,4,13,0,9 和 9。总和为 39。

标签： c++

解决方案

乍一看，肯定会发生让我们运行一个双循环直到每个元素的数组末尾并找到元素的总和。

粗略地说，这给了你 O(n2) 的复杂性 现在，你想3+4在你已经计算了第一次迭代的同时为第二次迭代添加（当你循环 2 时）？我不会...

因此，我会像这样保存这些增量添加： 

    for (int *i = ptr + l - 2; i >= ptr; i--) {
        *i = *i + *(i+1);
    }

这会给我{1,2,3,4} -> {10,9,7,4}

现在运行双循环：

    for (int *i = ptr; i < ptr + l; i++) {
        cout << *i << " ";
        for (int *j = i+1; j < ptr + l; j++) {
            cout << *i - *j << " ";
        }
    }

现在你有了所有的金额。您可以执行所有必需的操作。对于您的示例，第二小：您可以在该双循环中添加以下代码

        if (secondsmallest >= x) {
            if (smallest >= x) {
                secondsmallest = smallest;
                smallest = x;
            }else{
                secondsmallest = x;
            }
        }

找到正确的位置添加它并x用合适的符号替换:)

干杯......如果你觉得这个答案有帮助 - 考虑投票:)

推荐阅读