Find how many combinations are present in the given array which when summed, equals the given target value.
package abc;
import java.util.Arrays;
public class SumSubArray {
public static void main(String[] args) {
//find how
many combinations are present in the array with sum = target
//This problem is taken from LeetCode
//Solution
//sum each
index value from left to right.
//summed
value at an index x as we progress from left to right = x1
//Let’s say
x1-target = y1, the value at one of the previous index y
//Then the
target value is the sum of the values from index y+1 to x , count this
//OR if
x>=y and x1-target = 0, count this also
//suppose y1
is at index 8 and x1 is at index 6, and x1-target=y1, then sum of the index
values of 7, 8 = target value
int target = 9;
int[] num = {9,2,5,3,1,0,3,9,3,-4,1,2,1,4};
int l = num.length;
int[] sumAtindex = new int[l];
int sumValues = 0;
for(int i=0; i<l; i++) {
sumValues = sumValues+num[i];
sumAtindex[i] = sumValues;
}
System.out.println("Array with sum "+Arrays.toString(sumAtindex));//Array
with sum [9, 11, 16, 19, 20, 20, 23, 32, 35, 31, 32, 34, 35, 39]
int count = 0;
//Find the count
for(int i=0; i<l; i++) {
for(int j=0; j<l; j++) {
if(i>=j)
if((sumAtindex[i]-target==sumAtindex[j])||(sumAtindex[i]-target==0)) {
count++;
System.out.println("the indexValues are =
"+sumAtindex[i]+" "+sumAtindex[j]);
}
}
}
System.out.println("count = "+count);//5
}
}
Output:
Array with sum [9, 11, 16, 19, 20,
20, 23, 32, 35, 31, 32, 34, 35, 39]
the indexValues are = 9 9
the indexValues are = 20 11
the indexValues are = 20 11
the indexValues are = 32 23
the indexValues are = 32 23
count = 5