C++程序寻找给定和的子数组-1

给定一个未排序的非负整数数组，找到一个连续的子数组，使其总和为一个给定的数。

例子：

输入：arr[] = {1, 4, 20, 3, 10, 5}，sum = 33
输出：和找到在索引2和4之间
索引2到4之间的元素的总和为
20 + 3 + 10 = 33

输入：arr[] = {1, 4, 0, 0, 3, 10, 5}，sum = 7
输出：和找到在索引1和4之间
索引1到4之间的元素的总和为
4 + 0 + 0 + 3 = 7

输入：arr[] = {1, 4}，sum = 0
输出：未找到子数组
没有总和为0的子数组

满足给定和的子数组可能不止一个。以下解决方案打印第一个这样的子数组。

简单方法： 一种简单的解决方案是逐个考虑所有子数组并检查每个子数组的总和。以下程序实现简单的解决方案。运行两个循环：外循环选取起始点I，内循环尝试从i开始的所有子数组。

算法：

从前往后遍历数组。
从每个索引开始，从i到数组的结尾开始另一个循环，以获得从i开始的所有子数组，保留一个变量sum以计算总和。
对于内循环中的每个索引，更新 sum = sum + array [j]
如果总和等于给定的总和，则打印子数组。

// C++用于打印的简单程序
//具有给定和的子数组
#include
using命名空间std;
  
/ *如果有arr []的子数组，则返回true
    arr []的总和等于'sum'，否则
    返回false。另外，打印结果* /
int subArraySum(int arr []，int n，int sum)
{
    int curr_sum，i，j;
  
    //选择起始点
    为（i = 0; i  sum || j == n）
                休息;
            curr_sum = curr_sum + arr [j];
        }
    }
    cout <<“未找到子数组”;
    返回0;
}
  
//驱动器代码
int main()
{
    int arr [] = {15、2、4、8、
                 9、5、10、23};
    int n = sizeof（arr）/ sizeof（arr [0]）;
    int sum = 23;
    subArraySum（arr，n，sum）;
    返回0;
}
//这段代码由rathbhupendra贡献```

输出：

和找到在索引1和4之间

复杂度分析：

时间复杂度： 最坏情况下为O(n^2）。使用嵌套循环遍历数组，因此时间复杂度为O(n^2）。
空间复杂度： O(1)。需要常量的额外空间。

高效方法： 如果数组的所有元素均为正数，则可以考虑一个思想。如果一个子数组的总和大于给定的和，那么没有添加元素到当前子数组中的可能性，该总和将是x（给定的总和）。思路是使用滑动窗口的类似方法。从一个空的子数组开始，将元素添加到子数组中，直到总和小于x。如果总和大于x，则从当前子数组的开头删除元素。

算法：

创建三个变量， l = 0，sum = 0
从开头到结尾遍历数组。
通过添加当前元素来更新变量sum， sum = sum + array[i]
如果sum大于给定的sum，将变量sum更新为 sum = sum – array[l] ，并将l更新为，l++。
如果sum等于给定的sum，则打印子数组并跳出循环。

// C++ efficient program to print 
// subarray with sum as given sum 
#include <iostream>
using namespace std;

/* Returns true if the there is a subarray of 
   arr[] with a sum equal to 'sum' otherwise 
   returns false. Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
    /* Initialize curr_sum as value of 
       first element and starting point as 0 */
    int curr_sum = arr[0], start = 0, i;

    /* Add elements one by one to curr_sum and 
       if the curr_sum exceeds the sum,
       then remove starting element */
    for (i = 1; i <= n; i++) 
    {
        // If curr_sum exceeds the sum,
        // then remove the starting elements
        while (curr_sum > sum && start < i - 1) 
        {
            curr_sum = curr_sum - arr[start];
            start++;
        }

        // If curr_sum becomes equal to sum,
        // then return true
        if (curr_sum == sum) 
        {
            cout << "Sum found between indexes " << 
                     start << " and " << i - 1;
            return 1;
        }
        // Add this element to curr_sum
        if (i < n)
            curr_sum = curr_sum + arr[i];
    }
    // If we reach here, then no subarray
    cout << "No subarray found";
    return 0;
}

// Driver Code
int main()
{
    int arr[] = {15, 2, 4, 8, 
                 9, 5, 10, 23};
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 23;
    subArraySum(arr, n, sum);
    return 0;
}