максимальный подмассив, сумма которого равна 0

Question

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

Answer 1

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

Этот алгоритм найдет все подмассивы с суммой 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 sum будет иметь индекс от 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 ==> сумма tmp от 0 до 5 = 0, длина (5 - 0) + 1 = 6
• значение 3 в tmp для индекса 6 и 7 ==> сумма tmp от 7 до 7 = 0, длина (7 - 7) + 1 = 1

**** ОБНОВЛЕНИЕ ****

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

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

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

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

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

Answer 2

Это те же строки, которые предлагает Геворг, но я использовал хеш-карту для быстрого поиска.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);
}

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

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

Answer 3

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)

Answer 4

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

Начинается с каждого индекса массива, вычисляет и сравнивает отдельные суммы (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();
}

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

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

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

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

Answer 5

Вот реализация 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");            
    }           
}

Смотрите эксперимент здесь: http://rextester.com/PAKT41271

Answer 6

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

.

##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)

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

Answer 7

Другим решением этой проблемы может быть: 1. Рассчитать сумму для всего массива 2. Теперь следуйте следующей формуле, чтобы получить самый большой подмассив с нулевой суммой:

Math.max(find(a,l+1,r,sum-a[l]), find(a,l,r-1,sum-a[r]));
where l=left index, r= right index, initially their value=0 and a.length-1

Идея проста, максимальный размер, который мы можем получить с суммой = 0, это размер массива, тогда мы начинаем пропускать элементы слева и справа рекурсивно, в тот момент, когда мы получаем сумму = 0, мы останавливаемся. Ниже приведен код для того же:

static int find(int a[]) {
    int sum =0;
    for (int i = 0; i < a.length; i++) {
        sum = sum+a[i];
    }

    return find(a, 0, a.length-1, sum);
}


static int find(int a[], int l, int r, int sum) {
    if(l==r && sum>0) {
        return 0;
    }
    if(sum==0) {
        return r-l+1;
    }
    return Math.max(find(a,l+1,r,sum-a[l]), find(a,l,r-1,sum-a[r]));

}

Answer 8

Одно из решений:

Допустим, у нас есть массив целых чисел, int [] arr = {2,1, -1, -2};

Мы будем использовать цикл for, пока не найдем число <0 ИЛИ <= 0 я = 2; </p>

Во внутреннем цикле мы пройдем через присвоение значения j = i-1. Итак, мы можем найти положительное значение.

for(int i = 0; i<arr.length; i++){
      int j = 0;
      int sum = arr[i];
      if(arr[i] < 0){
      j = i - 1;
}

У нас будет одна переменная суммы, которая будет поддерживать сумму arr [i] и arr [j] и обновлять результат.

Если сумма <0, то нам нужно переместить левую часть массива и, таким образом, мы будем уменьшать j на единицу, j - </p>

for(j = i-1; j>=0; j--) {
      sum = sum + arr[j];
      if(sum == 0){
      System.out.println("Index from j=" + j+ " to i=" + i);
      return true;
   }
}

Если сумма> 0, тогда мы должны переместить правую часть массива и, таким образом, мы будем увеличивать i

Когда мы находим сумму == 0, мы можем напечатать индекс j и i и вернуть или разорвать цикл.

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

Answer 9

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

 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);
        }
   }        
}

Answer 10

Ниже коды могут найти каждый возможный подмассив, сумма которого равна заданному числу, и (конечно) он может найти самый короткий и самый длинный подмассив такого рода.

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 + "]");
}