Нужно найти непрерывные участки, где сумма элементов равна 0
Я написал начало кода, есть размер массива (300), а диапазон массива [-100, ..., 100)
ниже прикрепил начало кода. Помогите пожалуйста написать остальную часть, так как я пока что новичок в этом и не совсем разбираюсь.
public class Task3_1 {
public static void main(String[] args) {
int mass [] = new int[300];
for (int i = 0; i < mass.length; i++) {
mass[i] = ((int)(Math.random()*200) - 100);
}
int sum = 0;
for(int x : mass) {
}
}
}
Ответы (3 шт):
Автор решения: Alex Rudenko
→ Ссылка
Простейший способ -- полным перебором вычислить суммы для каждой подпоследовательности во входном массиве, вывести те, сумма которых равна 0 (или другому заданному значению), увеличить счётчик:
static int countSubarrays(int sum, int ... arr) {
int count = 0;
int n = arr.length;
for (int i = 0; i < n; i++) {
int subTotal = 0;
for (int j = i; j < n; j++) {
subTotal += arr[j];
if (subTotal == sum) {
count++;
System.out.println(subArr(i, j, arr));
}
}
}
return count;
}
Метод subArr возвращает подпоследовательность между двумя индексами в виде строки для печати:
static String subArr(int from, int to, int ... arr) {
StringBuilder sb = new StringBuilder();
sb.append('[').append(from).append("; ").append(to).append("]:");
for (int i = from; i <= to; i++) {
sb.append(" ").append(arr[i]);
}
return sb.toString();
}
Тест: для диапазона значений [-15; 15], 30 чисел:
Random random = ThreadLocalRandom.current();
int[] arr = random.ints(30, -15, 16).toArray();
System.out.println(Arrays.toString(arr) + "\n----");
System.out.println("Found " + countSubarrays(0, arr));
Результат:
[-3, 15, -11, 13, 8, -13, 5, 8, 13, 1, -2, -11, 9, 15, -6, 13, 4, -8, 13, 12, -12, 1, -8, 15, -7, -13, -10, -11, 9, 3]
----
[4; 6]: 8 -13 5
[5; 7]: -13 5 8
[15; 26]: 13 4 -8 13 12 -12 1 -8 15 -7 -13 -10
[19; 20]: 12 -12
[22; 24]: -8 15 -7
Found 5
Автор решения: Adm123
→ Ссылка
public class FindInArr {
private static final int[] testArr = {1,2,3,-6,3,-3,-4,-5,-6,-7};
public static void main(String[] args) {
printZeroSumParts(testArr);
}
public static int arraySum(int[] arr) {
if (arr == null) {
throw new IllegalArgumentException();
}
int sum = 0;
for (int i : arr) {
sum += i;
}
return sum;
}
public static int[] getSubArray(int[] arr, int firstIndex, int lastIndex) {
if (arr == null || lastIndex < firstIndex || firstIndex < 0) {
throw new IllegalArgumentException();
}
int[] destArr = new int[lastIndex - firstIndex];
System.arraycopy(arr, firstIndex, destArr, 0, lastIndex - firstIndex);
return destArr;
}
public static void printZeroSumParts(int[] arr) {
if (arr == null || arr.length == 0) {
throw new IllegalArgumentException();
}
if (arr.length == 1) {
if (arr[0] == 0) {
System.out.println(Arrays.toString(arr));
}
return;
}
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length - 1; j++) {
int[] candidate = getSubArray(arr, i, j);
if (arraySum(candidate) == 0) {
System.out.println(Arrays.toString(candidate));
}
}
}
}
}
Автор решения: Stanislav Volodarskiy
→ Ссылка
Алгоритм предложил Akina в комментариях к ответу - сортировка накопительных сумм, печать отрезков для равных накопительных сумм.
Сложность N·logN + K, где K - объём печати. Если печатать подсписки то K ≤ N3 (так сделано сейчас). Если печатать только диапазоны индексов, то K ≤ N2. Можно поменять формат печати так что окажется K ≤ N а все диапазоны будут напечатаны. Если требуется только сосчитать количество диапазонов, то K ≤ N (общая сложность N·logN).
Вместо сортировки одинаковые накопительные суммы можно накапливать в HashMap. Сложность будет N + K.
Код:
import java.util.Arrays;
public class Task3_1 {
private static class Item implements Comparable<Item> {
public final int index;
public final long value;
public Item(int index, long value) {
this.index = index;
this.value = value;
}
@Override
public int compareTo(Item other) {
return Long.compare(value, other.value);
}
}
public static void main(String... args) {
// make random array
final int max = 20;
int array[] = new int[40];
for (int i = 0; i < array.length; ++i) {
array[i] = ((int)(Math.random() * 2 * max) - max);
}
// print array
for (int i = 0; i < array.length; ++i) {
System.out.print(" " + array[i]);
}
System.out.println();
// accumulate sums
Item sums[] = new Item[array.length + 1];
sums[0] = new Item(0, 0);
for (int i = 0; i < array.length; ++i) {
sums[i + 1] = new Item(i + 1, sums[i].value + array[i]);
}
// sort to group equal sums
Arrays.sort(sums);
// print all pairs of equal sums
for (int i = 0; i < sums.length; ++i) {
for (
int j = i + 1;
j < sums.length && sums[i].value == sums[j].value;
++j
) {
System.out.print(
"[" + sums[i].index + ", " + sums[j].index + "):"
);
for (int k = sums[i].index; k < sums[j].index; ++k) {
System.out.print(" " + array[k]);
}
System.out.println();
}
}
}
}
Тесты:
$ javac Task3_1.java $ java Task3_1 12 -16 -11 -7 0 -6 -5 14 -5 16 -6 -19 14 12 -7 -9 19 -4 -13 -18 -9 4 -8 -5 7 -3 19 -8 8 5 -6 -14 -11 9 -5 13 -3 18 19 11 [27, 29): -8 8 [7, 12): 14 -5 16 -6 -19 [6, 38): -5 14 -5 16 -6 -19 14 12 -7 -9 19 -4 -13 -18 -9 4 -8 -5 7 -3 19 -8 8 5 -6 -14 -11 9 -5 13 -3 18 [4, 5): 0 [8, 13): -5 16 -6 -19 14 [11, 15): -19 14 12 -7 [10, 18): -6 -19 14 12 -7 -9 19 -4 [2, 17): -11 -7 0 -6 -5 14 -5 16 -6 -19 14 12 -7 -9 19 $ java Task3_1 -3 16 8 1 19 6 9 19 5 -5 -5 -18 10 9 1 -7 10 -2 2 14 7 -18 -1 -18 3 8 -7 9 -2 12 0 -20 -2 18 -20 0 -15 -6 3 -11 [35, 36): 0 [13, 25): 9 1 -7 10 -2 2 14 7 -18 -1 -18 3 [13, 32): 9 1 -7 10 -2 2 14 7 -18 -1 -18 3 8 -7 9 -2 12 0 -20 [25, 32): 8 -7 9 -2 12 0 -20 [11, 26): -18 10 9 1 -7 10 -2 2 14 7 -18 -1 -18 3 8 [11, 29): -18 10 9 1 -7 10 -2 2 14 7 -18 -1 -18 3 8 -7 9 -2 [26, 29): -7 9 -2 [15, 28): -7 10 -2 2 14 7 -18 -1 -18 3 8 -7 9 [8, 10): 5 -5 [8, 17): 5 -5 -5 -18 10 9 1 -7 10 [8, 19): 5 -5 -5 -18 10 9 1 -7 10 -2 2 [10, 17): -5 -18 10 9 1 -7 10 [10, 19): -5 -18 10 9 1 -7 10 -2 2 [17, 19): -2 2 [22, 34): -1 -18 3 8 -7 9 -2 12 0 -20 -2 18 [30, 31): 0