JavaRush /Java блог /Архив info.javarush /Кухня(); Задание N63

28 уровень

30 сентября 2014
2507 views
16 comments

Кухня(); Задание N63

Правила [Одномерные массивы] 63. Дан целочисленный массив А и число М. Найти такое подмножество подряд идущих элементов массива, сумма значений элементов, которых равна М.

Комментарии (16)

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ

Vash_the_Stampede Уровень 11

1 октября 2014

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

LastLost Уровень 41

1 октября 2014

лучше :)

Docktor91 Уровень 40

1 октября 2014

отлично!

Airon Уровень 34

1 октября 2014

public static int[] getSeqM(int m, int... a) {
    int[] seq = new int[0];
    for (int i = 0; i < a.length - 1; i++) {
        int sumM = a[i];
        if(sumM >= m) continue;
        for (int j = i + 1; j < a.length; j++) {
            sumM += a[j];
            if(sumM == m) {
                seq = Arrays.copyOf(seq, seq.length + (j - i + 1));
                for (int k = 0; k < j - i + 1; k++) 
                    seq[seq.length - (j - i + 1) + k] = a[i + k];
                break;
            } else if(sumM > m) break;
        }
    }
    return seq;
}

Docktor91 Уровень 40

1 октября 2014

а одним циклом слабо?)))

Airon Уровень 34

1 октября 2014

ну так как куча continue and break — не думаю, что много можно выиграть инкрементами переменных в одном форе.
А так вызов принят!, но завтра уже =).

Docktor91 Уровень 40

1 октября 2014

LastLost Уровень 41

1 октября 2014

а такой вопрос — только одно подмножество или все?

LastLost Уровень 41

1 октября 2014

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

Airon Уровень 34

1 октября 2014

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 следующий элемент и дальше дальше может быть отрицательным и как то выровнять это колебание.
Попытки были неудачны так что в долгий ящик…

Airon Уровень 34

1 октября 2014

Например из массива [8, 7, 1, 1, 4, 8, 7, 0, 0, 0, -6, 0, 9, 6, 0, 1, 3, 1, 4, 4] находить М = 9, должно найти все варианты, такие как:
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

public static int[] getSeqM(int m, int... a) {    
    int[] seq = new int[0];
    for (int i = 0; i < a.length; i++) {
        int sumM = a[i];
        int length = a.length;
        for (int j = i + 1; j < length; j++) {
            sumM += a[j];
            if(j + 1 == length) {
                if(sumM == m) {
                    seq = Arrays.copyOf(seq, seq.length + (j - i + 1));
                    for (int k = 0; k < (j - i + 1); k++)
                        seq[seq.length - (j - i + 1) + k] = a[i + k];                     
                }
                length--;
                sumM = a[j = i];
                continue;
            }
        }
    }
    return seq;
}

LastLost Уровень 41

2 октября 2014

Для всех вариантов надо вместо сброса начинать новый отсчет. В один цикл можно втиснуть

Airon Уровень 34

2 октября 2014

Ну так на словах все просто — мне надоело мучатся, я хотел бы посмотреть чужой рабочий вариант решения, но его пока в топике нет, подожду, ведь цель топика "научиться у сильных".

LastLost Уровень 41

2 октября 2014

Ищет все последовательности

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

Airon Уровень 34

2 октября 2014

Ну так опять же громкое слово «все» из примера приведенного выше ваш метод выдал:
[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
Так то все круто и мне точку зрения решения задачи изменили.

LastLost Уровень 41

2 октября 2014

подряд идущих элементов

кагбе намекает
и один элемент тоже может быть последовательностью.