时间戳

首页 > 解决方案 > 给定和未排序的数组 arr ，大小为 n 的非负整数，找到一个连续子数组，它添加到数字总和。帮助获得输出

c++ - 给定和未排序的数组 arr ，大小为 n 的非负整数，找到一个连续子数组，它添加到数字总和。帮助获得输出

问题描述

#include <iostream>

using namespace std;

int main()
{
int n;
n=4;
int arr[n]={1,2,3,8};
int sum;
sum=5;
int curr=0;
cin>>sum;
for(int i=0;i<n;i++){
    for(int j=i;j<n;j++){
        curr+=arr[j];
        if(curr==sum){
            cout<<i;
        }
    cout<<curr<<endl;
    }
}
    
}

对于给定的问题，我需要找到这样一个子数组的开始和结束索引。我已经尝试了上面的代码，但无法获得正确的输出。请指导我。

标签： c++arrayscoutsub-array

解决方案

我认为您的代码只需要一些小的修改。您应该添加一些代码来处理运行总和大于目标总和的情况，并且您还应该正确地重新初始化运行总和。

可能有一些比O(n^2)更快的有效解决方案，我还不知道。如果有人知道时间复杂度更高的解决方案，请与我们分享。

下面是一个时间复杂度为O(n^2)的简单算法。（对于这个问题，它可能没有最有效的时间复杂度）。

此函数打印出数组的 2 个索引。这两个索引之间的所有元素的总和将等于目标总和。

    void Print_Index_of_2_Elements(int array[], int total_element, int target)
    {            
            // Use Brute force .  Time complexity = O(n^2)
            for (int i = 0; i < total_element; i++) 
            {
                int running_sum = array[i];
        
                // Second for loop
                for (int j = (i + 1) ; j < total_element; j++) 
                {
                    if (running_sum == target) 
                    {    
                        cout << "Two indices are: " << i << " and " << j;
                        return;  // Found Answer. Exit.
                    }
                    else if ( running_sum > target )
                        break;
                    else  //  running_sum < target 
                        running_sum += array[j];
                }
            }
        
            cout << " Sorry - no answer was found for the target sum.";             
}

推荐阅读