Проверка условий на элементах массива

Question

У меня есть массив чисел nums [] и цель, так что она удовлетворяет условию ниже {{nums [], target}

 1> {{8, 2, 2, 1},12} --> returns true       
 2> {{8, 2, 2, 1},9}  --> returns true        

 1 condition> identical adjacent values with a subset of remaining numbers sum to target (or)
 2 condition> identical adjacent values are not chosen such that subset of other numbers sum to target. 
so that in this example 
1> 8+2+2 = 12.
2> 8+1=9.

как мне обработать 2 вышеуказанных условия в Java.

РЕДАКТИРОВАНИЕ ДЛЯ ДАНТЕ:
Ожидается этот прогон
groupSumClump (0, {2, 4, 8}, 10) → true true OK
groupSumClump (0, {1, 2, 4, 8, 1}, 14) → true true OK
groupSumClump (0, {2, 4, 4, 8}, 14) → false false OK
groupSumClump (0, {8, 2, 2, 1}, 9) → true false X
groupSumClump (0, {8, 2, 2, 1}, 11) → false false OK
groupSumClump (0, {1}, 1) → true false X
groupSumClump (0, {9}, 1) → false false OK
другие тесты ложные X

* Код для Данте:
http://www.ideone.com/xz7ll

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

Answer 1

Я видел, как вы долго боролись с этим вопросом, поэтому вот несколько кодов ....

РЕДАКТИРОВАТЬ

    int nums_another[] = new int [nums.length];
    int i = 0;
    int j = 0;
    i++;
    int c = 1;
    while (i < nums.length){
        if (nums[i] == nums[i-1]) { // count identical numbers
            c++;
        }
        else { // not identical, store sum of previous identical numbers (possibly only 1 number)
            if (nums[i-1] != 0) {
                nums_another[j] = nums[i-1] * c;
                j++;
            }
            c = 1;
        }
        i++;
    }
    if (nums[i-1] != 0) { // store last
        nums_another [j] = nums[i-1] * c; 
    }

Теперь nums_another включает в себя:

• суммы групп смежных идентичных чисел (в вашем случае 4 = 2 + 2)

• не идентичных чисел (в вашем случае 8,1)

• 0, наконец (таким образом, всего 8 4 1 0)

---

Кстати, проблема с вашим кодомэто то, что:

, поскольку вы сразу устанавливаете следующее идентичное число на 0, оно не будет работать в течение 3 или более, например,

, 8 2 2 2 1 -> 8 4 0 2 1 вместоиз -> 8 6 0 0 1

Answer 2

Вы можете решить оба условия одновременно с двумя локальными переменными: набором «одиноких» чисел и аккумулятором для «смежных» значений:

Шаг по массиву.

Для каждого значенияпроверьте предыдущее значение (если оно есть) и следующее значение (если оно есть).

Если одно из них совпадает с текущим значением, увеличьте значение «соседнего» аккумулятора, в противном случае добавьте значениев набор «одиноких чисел».

Чтобы проверить условие 2, вычтите значение «соседнего» аккумулятора из цели, для условия 1 оставьте его без изменений.

Остальная часть проблемызаключается в том, чтобы определить, соответствует ли какое-то подмножество значений в «одиночном наборе» целевому значению.Это хорошо известная числовая задача, которую сложно вычислить (экспоненциальное усилие), но которую не сложно запрограммировать.Вы можете найти много решений, если вы ищете его имя: оно называется «проблема с рюкзаком».