在数组中查找具有给定总和的子数组。

Question

给定一个非负整数数组和一个数字。您需要打印总和等于给定整数的子数组的所有开始和结束索引。
例如 ：

Input-int[] arr = {2, 3, 6, 4, 9, 0, 11};
int num = 9
Output-
starting index : 1, Ending index : 2
starting index : 5, Ending index : 5
starting index : 5, Ending index : 6

Explanation :
[3, 6] [9],
[9,0] These all are the subarrays with their sum equal to 9.

Answer 1

解决这个问题的基本蛮力方法是生成给定数组的所有子数组，然后遍历生成的子数组并计算总和，如果这个总和等于给定的总和，则打印这个子数组，因为它是我们解决方案的一部分。

现在我们知道，一个有 n 个元素的数组有n*(n+1)/2 个子数组。

如何？
考虑一个数组，

                                      int[] arr = {a1, a2, a3, a4…, an};
Subarrays starting with 0th index,
a1
a1, a2
a1, a2, a3
a1, a2, a3, a4
.
.
.
a1, a2, a3, a4…, an

Subarrays starting with 1st index,
a2
a2, a3
a2, a3, a4
.
.
.
a2, a3, a4…, an

subarrays starting with 2nd index,
a3
a3, a4
.
.
.
a3, a4…, an

Subarrays starting with last i.e. 3rd index,
a4
.
.
.
a4…, an

现在，
总子数组= 从第 0 个 idx开始的子数组+从第 1 个 idx 开始的子数组+
从第 2 个 idx + 开始的子数组。. . + 以第 n 个 idx 开头的子数组

Sn = n + (n-1) + (n-2) + (n-3) + ... + 1

Sn = n(n+1)/2

在那里，生成所有子数组并计算答案将花费我们最坏的时间复杂度，O(n(n+1)/2)其顺序为O(n^2)。

package Arrays;

import java.util.Scanner;

public class targetsumSubarr {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];
        int target = scn.nextInt();

        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }

        solve(arr, target);

    }

    public static void solve(int[] arr, int target)
    {
        for(int start = 0; start < arr.length; start++)
        {
                 // initialize the sum of the current subarray to 0.
            int currSum = 0;
            for(int end = start; end < arr.length; end++)
            {
                // add every element of the current subarray
                // to the current running sum.
                currSum += arr[end];

               // print the starting and ending indices once we get
               // subarray with given sum
                if(currSum == target)
                {
                     System.out.println("starting index : " +
                                 start + ", " + "Ending index : " + end);

                }

            }
        }
    }

}

有效的方法：

我们可以在线性时间内解决这个问题，即O(n)最坏的时间复杂度。

我们可以维护两个指针，一个基本上代表一个子数组的指针，start并且end我们必须取一个变量来存储current sum从开始指针到结束指针的子数组的。

我们end在添加元素的同时不断增加指针，current sum直到我们到达当前运行总和大于所需目标总和的点，这基本上意味着我们计算出的总和不是正确答案的当前子数组。
所以现在我们通过移动start指针来改变我们的子数组，即缩短子数组，从而缩短当前总和，希望我们实现当前总和等于所需的目标总和。
在每一点我们检查我们当前的总和是否等于目标总和，如果是这种情况我们打印我们的指针。
所以基本上，我们通过增加改变子数组start和end指针和改变取决于它的价值相比，目标总电流总和。

package org.arpit.java2blog;

import java.util.Scanner;

public class TargetsumSubarr {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];
        int target = scn.nextInt();

        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }

        System.out.print("arr[]: {");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" "+arr[i]);
        }

        System.out.println(" }");
        solveEfficient(arr, target);

    }

    public static void solveEfficient(int[] arr, int target) {
        int start = 0, end = 0;

        int currSum = 0;

        while (start < arr.length && end <= arr.length) {
            if (currSum == target) {

                /* as the currSum is equal to target sum, print the 
                 * result with end as end-1.
                 *  because when we added the element at end we
                 *  increased the pointer there only,
                 *  so now we need to subtract 1 because the 
                 *  subarray constituting that sum has
                 *   its last pointer one index where end is currently at.
                 */

                System.out.println("starting index : " + start + ", " + 
                        "Ending index : " + (int) (end - 1));

                if (end <= arr.length - 1) {
                    currSum += arr[end];
                }
                end++;

            }

            else {
                /* if the currSum becomes more than required, 
                 * we keep on subtracting the start element
                 * until it is less than or equal to 
                 required target sum. */
                if (currSum > target) {
                    currSum -= arr[start];
                    start++;
                } else {
                    /* we add the last element to our
                     * currSum until our 
                     * sum becomes greater than or
                     * equal to target sum.
                     */
                    if (end <= arr.length - 1) {
                        currSum += arr[end];
                    }
                    end++;
                }
            }
        }
    }
}

当你运行上面的程序时，你会得到以下输出：

7
9
2 3 6 4 9 0 11
arr[]: { 2 3 6 4 9 0 11 }
starting index : 1, Ending index : 2
starting index : 4, Ending index : 4
starting index : 4, Ending index : 5