В массив входят как положительные, так и отрицательные элементы, найдите подмассива сумма равна 0.
Нулевая сумма SubArray
Ответ 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 будет от индекса 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).
Ответ 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 }
Ответ 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)
Ответ 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]
Ответ 5
Следующее решение находит макс. длину подматрицы с заданной суммой 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)
Сложность по времени - это O (n), а сложность пространства - O (n) из-за рекурсивного стека памяти
Ответ 6
Здесь реализация 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
Ответ 7
Массив содержит положительные и отрицательные числа. Найдите подматрицу с максимальной суммой
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
cumulativeSum=cumulativeSum+array[i];
if(cumulativeSum>max)
{
max=cumulativeSum;
savepoint=start;
end=i;
}
i++;
}
System.out.println("Max : "+max+" Start indices : "+savepoint+" end indices : "+end);
return max;
}
Ответ 8
Ниже кодов можно узнать все возможные подматрицы, у которых есть сумма, являющаяся заданным числом, и (конечно) она может найти самую короткую и самую длинную подобласть такого типа.
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 + "]");
}
Ответ 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);
}
}
}
Ответ 10
Надеюсь, это поможет.
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<DIM; i++) {
sum = v[i];
counter=0;
for (j=i+1; j<DIM;j++) {
sum += v[j];
counter++;
if (sum == 0) {
printf("Sub-array starting from index %d, length %d.\n",(j-counter),counter +1);
}
}
}