Правила[Одномерные массивы]
63. Дан целочисленный массив А и число М. Найти такое подмножество подряд идущих элементов массива, сумма значений элементов, которых равна М.
0
Комментарии (16)
популярные
новые
старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
public static int[] solve(int[] arr, int m) {
int sum = arr[0];
int i = 0, j = 1;
while (j < arr.length) {
if (sum < m) {
sum += arr[j++];
}
else if (sum > m) {
sum -= arr[i++];
}
else {
return Arrays.copyOfRange(arr, i, j);
}
}
return null;
}
public static int[] getSeqM(int m, int... a)
{
int start = 0;
int i = 0;
int sum = 0;
int j = 0;
int[] result = new int[a.length];
while (i < a.length) {
result[j] = a[i];
sum += a[i];
if (sum == m)
return Arrays.copyOf(result, j + 1);
if (sum > m) {
result = new int[a.length];
j = 0;
sum = 0;
start++;
i = start;
} else
{
i++;
j++;
}
}
return new int[0];
}
public static int[] getSeqM3(int m, int... a) {
int[] seq = new int[0];
int index = 0, sumM = 0;
for (int i = 1; i < a.length; i++) {
if(i == 1) {
i += index;
if(i >= a.length) break;
sumM = a[index];
if(sumM >= m) {
i = 0;
index++;
continue;
}
}
sumM += a[i];
if(sumM == m) {
seq = Arrays.copyOf(seq, seq.length + (i - index + 1));
for (int j = 0; j < (i - index + 1); j++)
seq[seq.length - (i - index + 1) + j] = a[index + j];
i = 0;
index++;
continue;
} else if(sumM > m || (i + 1) == a.length) {
i = 0;
index++;
continue;
}
}
return seq;
}
Наверно это тоже будет считаться не одним циклом, я не знаю как с одним и без continue. Скорее всего подожду вашего варианта. Да и решает этот и прошлый варианты не заглядывая в следующий элемент и дальше и дальше, а ведь там может быть один или пачка нулей. Или когда сумма >= M следующий элемент и дальше дальше может быть отрицательным и как то выровнять это колебание.
Попытки были неудачны так что в долгий ящик…
Ну так на словах все просто — мне надоело мучатся, я хотел бы посмотреть чужой рабочий вариант решения, но его пока в топике нет, подожду, ведь цель топика "научиться у сильных".
public static List<int[]> getSeqM(int m, int... a)
{
List<int[]> resultList = new LinkedList<>();
int start = 0;
int i = 0;
int sum = 0;
int j = 0;
int[] result = new int[a.length];
while (i < a.length) {
result[j] = a[i];
sum += a[i];
if (sum >= m) {
if (sum == m)
resultList.add(Arrays.copyOf(result, j+1));
result = new int[a.length];
j = 0;
sum = 0;
start++;
i = start;
} else
{
i++;
j++;
}
}
return resultList;
}
А так вызов принят!, но завтра уже =).
Наверно это тоже будет считаться не одним циклом, я не знаю как с одним и без continue. Скорее всего подожду вашего варианта. Да и решает этот и прошлый варианты не заглядывая в следующий элемент и дальше и дальше, а ведь там может быть один или пачка нулей. Или когда сумма >= M следующий элемент и дальше дальше может быть отрицательным и как то выровнять это колебание.
Попытки были неудачны так что в долгий ящик…
7 1 1
8 7 0 0 0 -6 0
8 7 0 0 0 -6
0 0 0 -6 0 9 6 0
0 0 0 -6 0 9 6
0 0 -6 0 9 6 0
0 0 -6 0 9 6
0 -6 0 9 6 0
0 -6 0 9 6
-6 0 9 6 0
-6 0 9 6
0 9
0 1 3 1 4
1 3 1 4
1 4 4
[7, 1, 1]
[0, 0, 0, -6, 0, 9, 6]
[0, 0, -6, 0, 9, 6]
[0, -6, 0, 9, 6]
[-6, 0, 9, 6]
[0, 9]
[9] — это не последовательность!
[0, 1, 3, 1, 4]
[1, 3, 1, 4]
[1, 4, 4]
и где все остальные возможные случаи?:
8 7 0 0 0 -6 0
8 7 0 0 0 -6
0 0 0 -6 0 9 6 0
0 0 -6 0 9 6 0
0 0 -6 0 9 6
0 -6 0 9 6 0
-6 0 9 6 0
Так то все круто и мне точку зрения решения задачи изменили.
и один элемент тоже может быть последовательностью.