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

Question

#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;
    }
}
    
}

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

Answer 1

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

可能有一些比 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.";             
}

Answer 2

如果您是子数组或数组的初学者。那么这个代码是给你的：

#include <iostream>

using namespace std;

int main()
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
    cin>>arr[i];
}
int sum;
cin>>sum;
int curr=0;
for(int i=0;i<n;i++){
    for(int j=i;j<n;j++){
        if(curr==sum){
            cout<<i+1<<" "<<j;
            return 0;
        }
        else if (curr>sum){
            curr=0;
        }
        else if(curr<sum){
            curr+=arr[j];
        }

    }
}
return 0;
}

如果您对此有任何疑问，请随时发表评论让我知道。

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

Given and unsorted array arr , of size n of non-negative integers, find a continuous subarray which adds to number sum. Help in getting output

c++

arrays

cout

sub-array