Нулевая сумма SubArray

В массив входят как положительные, так и отрицательные элементы, найдите подмассива сумма равна 0.

10 ответов

Ссылка в текущем принятом ответе требует подписаться на членство, а я не его содержимое.

Этот алгоритм найдет все подмассивы с суммой 0, и его можно легко изменить, чтобы найти минимальный или отслеживать начальные и конечные индексы. Этот алгоритм O (n).

Учитывая массив int[] input, вы можете создать массив int[] tmp, где tmp[i] = tmp[i - 1] + input[i]; Каждый элемент tmp будет хранить сумму ввода до этого элемента (префиксная сумма массива).

Теперь, если вы проверите tmp, вы заметите, что могут быть значения, равные друг другу. Скажем, что эти значения находятся в индексах j an k with j < k, тогда сумма ввода до j равна сумме до k, а это означает, что сумма части массива между j и k 0! В частности, субам суммы 0 будет от индекса j + 1 до k.

  • ПРИМЕЧАНИЕ: если j + 1 == k, то k is 0 и что это!;)
  • ПРИМЕЧАНИЕ. Алгоритм должен учитывать виртуальный tmp[-1] = 0;
  • ПРИМЕЧАНИЕ. Пустой массив имеет сумму 0 и минимален, и этот особый случай должен быть поднят также в интервью. Тогда собеседник скажет, что это не значит, что это еще одна проблема!;)

Реализация может быть выполнена по-разному, включая использование HashMap с парами, но будьте осторожны со специальным случаем в разделе NOTE выше.

Пример:

int[] input = {4, 6, 3, -9, -5, 1, 3, 0, 2}
int[] tmp = {4, 10, 13, 4, -1, 0, 3, 3, 5}
  • Значение 4 в tmp при индексе 0 и 3 == > сумма tmp 1 до 3 = 0, длина (3 - 1) + 1 = 3
  • Значение 0 в tmp при индексе 5 == > sum tmp 0 to 5 = 0, length (5 - 0) + 1 = 6
  • Значение 3 в tmp при индексе 6 и 7 == > sum tmp 7 to 7 = 0, length (7 - 7) + 1 = 1

**** **** UPDATE

Предполагая, что в нашем массиве tmp мы получим несколько элементов с одинаковым значением, тогда вам нужно рассмотреть каждую идентичную пару! Пример (помните о виртуальном "0" в индексе "-1" ):

int[] array = {0, 1, -1, 0}
int[] tmp = {0, 1, 0, 0}

Применяя тот же алгоритм, описанный выше, подмассивы с суммой 0 суммируются с помощью следующих индексов (включая):

[0] [0-2] [0-3] [1-2] [1-3] [3]

Хотя наличие нескольких записей с одинаковым значением может повлиять на сложность алгоритма в зависимости от реализации, я считаю, что, используя инвертированный индекс для tmp (сопоставление значения с индексами, где он появляется), мы можем сохранить время работы в точке O (n).


Это одна и та же линия, предложенная Геворг, но я использовал хэш-карту для быстрого поиска. O (n) сложность использовала дополнительное пространство.

private static void subArraySumsZero()
{
 int [] seed = new int[] {1,2,3,4,-9,6,7,-8,1,9};
 int currSum = 0;
 HashMap<integer, integer=""> sumMap = new HashMap<integer, integer="">();
 for(int i = 0 ; i < seed.length ; i ++)
 {
 currSum += seed[i];
 if(currSum == 0)
 {
 System.out.println("subset : { 0 - " + i + " }");
 }
 else if(sumMap.get(currSum) != null)
 {
 System.out.println("subset : { " 
 + (sumMap.get(currSum) + 1) 
 + " - " + i + " }");
 sumMap.put(currSum, i);
 }
 else
 sumMap.put(currSum, i);
 }
 System.out.println("HASH MAP HAS: " + sumMap);
}
</integer,></integer,>

Созданный результат имеет индекс элементов (основанный на нуле):

subset : { 1 - 4 }
subset : { 3 - 7 }
subset : { 6 - 8 }


1. Given A[i]
 A[i] | 2 | 1 | -1 | 0 | 2 | -1 | -1
-------+---|----|--------|---|----|---
sum[i] | 2 | 3 | 2 | 2 | 4 | 3 | 2
2. sum[i] = A[0] + A[1] + ...+ A[i]
3. build a map<integer, set="">
4. loop through array sum, and lookup map to get the set and generate set, and push <sum[i], i=""> into map.
Complexity O(n)
</sum[i],></integer,>


Вот моя реализация, это очевидный подход, поэтому он, вероятно, под оптимизирован, но по крайней мере его ясный. Пожалуйста, поправьте меня, если я ошибаюсь.

Запускается из каждого индекса массива и вычисляет и сравнивает отдельные суммы (tempsum) с нужной суммой (в данном случае sum = 0). Поскольку целые числа подписаны, мы должны вычислить каждую возможную комбинацию.

Если вам не нужен полный список вспомогательных массивов, вы всегда можете поместить условия во внутренний цикл, чтобы вырваться из него. (Скажем, вы просто хотите знать, существует ли подобный массив, просто верните true, когда tempsum = sum).

public static string[] SubArraySumList(int[] array, int sum)
{
 int tempsum;
 List<string> list = new List<string>();
 for (int i = 0; i < array.Length; i++)
 {
 tempsum = 0;
 for (int j = i; j < array.Length; j++)
 {
 tempsum += array[j];
 if (tempsum == sum)
 {
 list.Add(String.Format("[{0}-{1}]", i, j));
 }
 }
 }
 return list.ToArray();
}
</string></string>

Вызов функции:

int[] array = SubArraySumList(new int { 0, -1, 1, 0 }, 0));

Печать содержимого выходного массива:

[0-0], [0-2], [0-3], [1-2], [1-3], [3-3]


Следующее решение находит макс. длину подматрицы с заданной суммой k без использования динамического программирования, но с использованием простой рекурсии. Здесь i_s является начальным индексом, а i_e - конечным индексом для текущего значения sum

##Input the array and sum to be found(0 in your case)
a = map(int,raw_input().split())
k = int(raw_input())
##initialize total sum=0
totalsum=0
##Recursive function to find max len 0
def findMaxLen(sumL,i_s,i_e):
 if i_s<len(a)-1 and="" i_e="">0: 
 if sumL==k:
 print i_s, i_e
 return (i_s,i_e)
 else:
 x = findMaxLen(sumL-a[i_s],i_s+1,i_e)
 y = findMaxLen(sumL-a[i_e],i_s,i_e-1)
 if x[1]-x[0]>y[1]-y[0]:
 return x
 else:
 return y
 else:
 ##Result not there
 return (-1,-1)
## find total sum
for i in range(len(a)):
 totalsum += a[i]
##if totalsum==0, max array is array itself
if totalsum == k:
 print "seq found at",0,len(a)-1
##else use recursion
else:
 print findMaxLen(totalsum,0,len(a)-1)
</len(a)-1>

Сложность по времени - это O (n), а сложность пространства - O (n) из-за рекурсивного стека памяти


Здесь реализация O(n) в java

Идея состоит в том, чтобы итерировать данный массив и для каждого элемента arr[i], вычислить сумму элементов от 0 до i, сохранить каждый sum в HashMap.

  • Если элемент 0, он рассматривается как вспомогательный массив ZeroSum.

  • если sum стал 0, тогда есть подвариантный массив ZeroSum, от 0 до i.

  • Если текущая сумма была замечена раньше в HashMap, тогда есть дополнительный массив ZeroSum, от этой точки до i.

код:

import java.util.*;
import java.lang.*;
class Rextester
{ 
 private static final int[] EMPTY = {};
 // Returns int[] if arr[] has a subarray with sero sum
 static int[] findZeroSumSubarray(int arr[])
 {
 if (arr.length == 0) return EMPTY;
 // Creates an empty hashMap hM
 HashMap<integer, integer=""> hM = new HashMap<integer, integer="">();
 // Initialize sum of elements
 int sum = 0; 
 for (int i = 0; i < arr.length; i++)
 { 
 sum += arr[i]; 
 if (arr[i] == 0) //Current element is 0
 {
 return new int[]{0}; 
 }
 else if (sum == 0) // sum of elements from 0 to i is 0
 {
 return Arrays.copyOfRange(arr, 0, i+1);
 }
 else if (hM.get(sum) != null) // sum is already present in hash map
 {
 return Arrays.copyOfRange(arr, hM.get(sum)+1, i+1);
 }
 else
 {
 // Add sum to hash map
 hM.put(sum, i);
 }
 } 
 // We reach here only when there is no subarray with 0 sum
 return null;
 } 
 public static void main(String arg[])
 {
 //int arr[] = {};
 int arr[] = { 2, -3, 1, 4, 6}; //Case left
 //int arr[] = { 0, 2, -3, 1, 4, 6}; //Case 0
 //int arr[] = { 4, 2, -3, 1, 4}; // Case middle
 int result[] = findZeroSumSubarray(arr);
 if (result == EMPTY){
 System.out.println("An empty array is ZeroSum, LOL"); 
 }
 else if ( result != null){
 System.out.println("Found a subarray with 0 sum :" );
 for (int i: result) System.out.println(i);
 }
 else
 System.out.println("No Subarray with 0 sum"); 
 } 
}
</integer,></integer,>

Пожалуйста, смотрите здесь эксперимент: http://rextester.com/PAKT41271


Ниже кодов можно узнать все возможные подматрицы, у которых есть сумма, являющаяся заданным числом, и (конечно) она может найти самую короткую и самую длинную подобласть такого типа.

public static void findGivenSumSubarray(int arr[], int givenSum) {
 int sum = 0;
 int sStart = 0, sEnd = Integer.MAX_VALUE - 1; // Start & end position of the shortest sub-array
 int lStart = Integer.MAX_VALUE - 1, lEnd = 0; // Start & end position of the longest sub-array
 HashMap<integer, arraylist<integer="">> sums = new HashMap<>();
 ArrayList<integer> indices = new ArrayList<>();
 indices.add(-1);
 sums.put(0, indices);
 for (int i = 0; i < arr.length; i++) {
 sum += arr[i];
 indices = sums.get(sum - givenSum);
 if(indices != null) {
 for(int index : indices) {
 System.out.println("From #" + (index + 1) + " to #" + i);
 }
 if(i - indices.get(indices.size() - 1) < (sEnd - sStart + 1)) {
 sStart = indices.get(indices.size() - 1) + 1;
 sEnd = i;
 }
 if(i - indices.get(0) > (lEnd - lStart + 1)) {
 lStart = indices.get(0) + 1;
 lEnd = i;
 }
 }
 indices = sums.get(sum);
 if(indices == null) {
 indices = new ArrayList<>();
 }
 indices.add(i);
 sums.put(sum, indices);
 }
 System.out.println("Shortest sub-arry: Length = " + (sEnd - sStart + 1) + ", [" + sStart + " - " + sEnd + "]");
 System.out.println("Longest sub-arry: Length = " + (lEnd - lStart + 1) + ", [" + lStart + " - " + lEnd + "]");
}
</integer></integer,>


Надеюсь, что это поможет вам.

private static void subArrayZeroSum(int array[] , int findSum){
 Map<integer,hashset<integer>> map = new HashMap<integer,hashset<integer>>();
 int sum = 0;
 for(int index = 0 ; index < array.length ; index ++){
 sum +=array[index];
 if(array[index] == findSum){
 System.out.println(" ["+index+"]");
 }
 if(sum == findSum && index > 0){
 System.out.println(" [ 0 , "+index+" ]");
 }
 if(map.containsKey(sum)){
 HashSet<integer> set = map.get(sum);
 if(set == null)
 set = new HashSet<integer>();
 set.add(index);
 map.put(sum, set);
 for(int val : set){
 if(val + 1 != index && (val + 1) < index){
 System.out.println("["+(val + 1) +","+index+" ]");
 }
 }
 }else{
 HashSet<integer> set = map.get(sum);
 if(set == null)
 set = new HashSet<integer>();
 set.add(index);
 map.put(sum, set);
 }
 } 
}
</integer></integer></integer></integer></integer,hashset<integer></integer,hashset<integer>


Массив содержит положительные и отрицательные числа. Найдите подматрицу с максимальной суммой

public static int findMaxSubArray(int[] array)
{
 int max=0,cumulativeSum=0,i=0,start=0,end=0,savepoint=0;
 while(i<array.length) {="" if(cumulativesum+array[i]<0)="" cumulativesum="0;" savepoint="start;" start="i+1;" }="" else="" if(cumulativesum="">max)
 {
 max=cumulativeSum;
 savepoint=start;
 end=i;
 }
 i++;
 }
 System.out.println("Max : "+max+" Start indices : "+savepoint+" end indices : "+end);
 return max;
}
</array.length)>


Надеюсь, это поможет.

int v[DIM] = {2, -3, 1, 2, 3, 1, 4, -6, 7, -5, -1};
int i,j,sum=0,counter=0;
 for (i=0; i

licensed under cc by-sa 3.0 with attribution.