algorithm - pseint - diagrama de flujo cuadrado magico

Dada una matriz de entrada, encuentra todos los subarrays con una suma dada K

Question

Dada una matriz de entrada, podemos encontrar una única sub-matriz que suma K (dada) en tiempo lineal, al hacer un seguimiento de la suma encontrada hasta ahora y la posición inicial. Si la suma actual es mayor que la K, seguimos eliminando elementos de la posición inicial hasta que obtengamos la suma actual <= K.

Encontré código de muestra de geeksforgeeks y lo actualicé para devolver todos los conjuntos posibles. Pero el supuesto es que la matriz de entrada consta de solo + ve números.

bool subArraySum(int arr[], int n, int sum)
{
int curr_sum = 0, start = 0, i;
bool found = false;
for (i = 0; i <= n; i++)
{
while (curr_sum > sum && start < i)
{
curr_sum = curr_sum - arr[start];
start++;
}
if (curr_sum == sum)
{
cout<<"Sum found in b/w indices: "<<start<<" & "<<(i-1)<<"/n";
curr_sum -= arr[start];
start++;
found = true;
}
// Add this element to curr_sum
if (i < n) {
curr_sum = curr_sum + arr[i];
}
}
return found;
}

Mi pregunta es: ¿también tenemos una solución para un conjunto mixto de números (tanto números positivos como negativos)?

Answer 1

Este problema es muy similar al problema de combinación resuelto aquí: http://introcs.cs.princeton.edu/java/23recursion/Combinations.java.html

Aquí está mi solución:

public static void main(String[] args) {
int [] input = {-10, 0, 5, 10, 15, 20, 30};
int expectedSum = 20;
combination(new SumObj(new int[0]), new SumObj(input), expectedSum);
}
private static void combination(SumObj prefixSumObj, SumObj remainingSumObj, int expectedSum){
if(prefixSumObj.getSum() == expectedSum){
System.out.println(Arrays.toString(prefixSumObj.getElements()));
}
for(int i=0; i< remainingSumObj.getElements().length ; i++){
// prepare new prefix
int [] newPrefixSumInput = new int[prefixSumObj.getElements().length + 1];
System.arraycopy(prefixSumObj.getElements(), 0, newPrefixSumInput, 0, prefixSumObj.getElements().length);
newPrefixSumInput[prefixSumObj.getElements().length] = remainingSumObj.getElements()[i];
SumObj newPrefixSumObj = new SumObj(newPrefixSumInput);
// prepare new remaining
int [] newRemainingSumInput = new int[remainingSumObj.getElements().length - i - 1];
System.arraycopy(remainingSumObj.getElements(), i+1, newRemainingSumInput, 0, remainingSumObj.getElements().length - i - 1);
SumObj newRemainingSumObj = new SumObj(newRemainingSumInput);
combination(newPrefixSumObj, newRemainingSumObj, expectedSum);
}
}
private static class SumObj {
private int[] elements;
private int sum;
public SumObj(int[] elements) {
this.elements = elements;
this.sum = computeSum();
}
public int[] getElements() {
return elements;
}
public int getSum() {
return sum;
}
private int computeSum(){
int tempSum = 0;
for(int i=0; i< elements.length; i++){
tempSum += elements[i];
}
return tempSum;
}
}

Answer 2

No existe un algoritmo de tiempo lineal para el caso de números positivos y negativos.

Como necesita todas las subarreglas que suman K , la complejidad de tiempo de cualquier algoritmo no puede ser mejor que el tamaño del conjunto resultante de subarreglas. Y este tamaño puede ser cuadrático. Por ejemplo, cualquier sub-array de [K, -K, K, -K, K, -K, ...] , que comienza y termina en ''K'' positivo tiene la suma requerida, y hay N 2/8 como subarreglos.

Aún así, es posible obtener el resultado en el tiempo O (N) esperado si hay espacio adicional O (N) disponible.

Calcule la suma de prefijos para cada elemento de la matriz e inserte el par (prefix_sum, index) en un mapa hash, donde prefix_sum es la clave y el index es el valor asociado con esta clave. Busque prefix_sum - K en este mapa hash para obtener uno o varios índices de matriz donde comienzan los prefix_sum - K resultantes:

hash_map[0] = [-1]
prefix_sum = 0
for index in range(0 .. N-1):
prefix_sum += array[index]
start_list = hash_map[prefix_sum - K]
for each start_index in start_list:
print start_index+1, index
start_list2 = hash_map[prefix_sum]
start_list2.append(index)

Answer 3

Prueba este código esto puede funcionar para ti:

private static void printSubArrayOfRequiredSum(int[] array, int requiredSum) {
for (int i = 0; i < array.length; i++) {
String str = "[ ";
int sum = 0;
for (int j = i; j < array.length; j++) {
sum = sum + array[j];
str = str + array[j] + ", ";
if (sum == requiredSum) {
System.out.println(" sum : " + sum + " array : " + str
+ "]");
str = "[ ";
sum = 0;
}
}
}
}

Utilice este método como:

 int array[] = { 3, 5, 6, 9, 14, 8, 2, 12, 7, 7 };
printSubArrayOfRequiredSum(array, 14);

Salida:

sum : 14 array : [ 3, 5, 6, ]
sum : 14 array : [ 14, ]
sum : 14 array : [ 2, 12, ]
sum : 14 array : [ 7, 7, ]

Answer 4

Solución dada por @Evgeny Kluev codificada en Java con una pequeña explicación.

public static void main(String[] args) {
int[] INPUT = {5, 6, 1, -2, -4, 3, 1, 5};
printSubarrays(INPUT, 5);
}
private static void printSubarrays(int[] input, int k) {
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
List<Integer> initial = new ArrayList<Integer>();
initial.add(-1);
map.put(0, initial);
int preSum = 0;
// Loop across all elements of the array
for(int i=0; i< input.length; i++) {
preSum += input[i];
// If point where sum = (preSum - k) is present, it means that between that
// point and this, the sum has to equal k
if(map.containsKey(preSum - k)) { // Subarray found
List<Integer> startIndices = map.get(preSum - k);
for(int start : startIndices) {
System.out.println("Start: "+ (start+1)+ "/tEnd: "+ i);
}
}
List<Integer> newStart = new ArrayList<Integer>();
if(map.containsKey(preSum)) {
newStart = map.get(preSum);
}
newStart.add(i);
map.put(preSum, newStart);
}
}

Answer 5

Solución dada por @Evgeny Kluev codificada en c ++

#include<bits/stdc++.h>
using namespace std;
int c=0;
// Function to print subarray with sum as given sum
void subArraySum(int arr[], int n, int k)
{
map<int,vector<int>>m1;
m1[0].push_back(-1);
int curr_sum=0;
for(int i=0;i<n;i++){
curr_sum=curr_sum+arr[i];
if(m1.find(curr_sum-k)!=m1.end()){
vector<int>a=m1[curr_sum-k];
c+=m1[curr_sum-k].size();
for(int j=0;j<a.size();j++){ // printing all indexes with sum=k
cout<<a[j]+1<<" "<<i<<endl;
}
}
m1[curr_sum].push_back(i);
}
}
int main()
{
int arr[] = {10,2,0,10,0,10};
int n = sizeof(arr)/sizeof(arr[0]);
int sum = 10;
subArraySum(arr, n, sum);
cout<<c<<endl; //count of subarrays with given sum
return 0;
}

Answer 6

También enfrenté este problema en un par de entrevistas y se me ocurrió el siguiente enfoque:

class MazSubArraySum {
public static void main(String[] args) {
int[] a = { -2, -3, 4, -1, -2, 1, 5, -3 };
System.out.println("Maximum contiguous sum is " + maxSubArraySum(a));
}
static int maxSubArraySum(int a[]) {
int size = a.length;
int currentindex = 0, end = 0, begin = 0;
int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;
for (int i = 0; i < size; i++) {
max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here) {
max_so_far = max_ending_here;
begin = currentindex;
end = i;
}
if (max_ending_here < 0) {
max_ending_here = 0;
currentindex++;
}
}
System.out.println("begin and end: " + begin + "&" + end);
return max_so_far;
}

}

A continuación se muestra la salida:

begin and end: 2&6
Maximum contiguous sum is 7

La solución anterior es la mejor solución en términos de complejidad de tiempo y espacio que es O (n).

Answer 7

Tiempo cuadrático: O (n2) en el peor de los casos.

private static void findSubArray(int[] is, int N) {
System.out.println("Continuous sub array of " + Arrays.toString(is) + " whose sum is " + N + " is ");
List<Integer> arry = new ArrayList<>(is.length);
for (int i = 0; i < is.length; i++) {
int tempI = is[i];
arry.add(tempI);
for (int j = i + 1; j < is.length; j++) {
if (tempI + is[j] == N) {
arry.add(is[j]);
System.out.println(arry);
} else if (tempI + is[j] < N) {
arry.add(is[j]);
tempI = tempI + is[j];
} else {
arry.clear();
break;
}
}
}
}
public static void main(String[] args) {
findSubArray(new int[] { 42, 15, 12, 8, 6, 32 }, 26);
findSubArray(new int[] { 12, 5, 31, 13, 21, 8 }, 49);
findSubArray(new int[] { 15, 51, 7, 81, 5, 11, 25 }, 41);
}