Сделайте суммы левой и правой сторон массива равными, удалив подмассив

Question

C программа, которая находит начальный и конечный индексы подмассива для удаления, чтобы сделать заданный массив равными суммами левой и правой сторон.Если это невозможно, выведите -1.Мне нужно, чтобы он работал для любого массива, это только для тестирования.Вот код, который находит равновесие.

#include <stdio.h> 

int equilibrium(int arr[], int n) 
{ 
int i, j; 
int leftsum, rightsum; 

/* Check for indexes one by one until 
an equilibrium index is found */
for (i = 0; i < n; ++i) {    

    /* get left sum */
    leftsum = 0; 
    for (j = 0; j < i; j++) 
        leftsum += arr[j]; 

    /* get right sum */
    rightsum = 0; 
    for (j = i + 1; j < n; j++) 
        rightsum += arr[j]; 

    /* if leftsum and rightsum are same, 
    then we are done */
    if (leftsum == rightsum) 
        return i; 
} 

/* return -1 if no equilibrium index is found */
return -1; 
} 

// Driver code 
int main() 
{ 
int arr[] = { -7, 1, 5, 2, -4, 3, 0 }; 
int arr_size = sizeof(arr) / sizeof(arr[0]); 
printf("%d", equilibrium(arr, arr_size)); 

getchar(); 
return 0; 
}

Answer 1

Вы можете решить эту проблему в O(NlogN) или O(N) (в среднем).

Сначала необходимо выполнить предварительную обработку, сохранив все суммы справа налево в данныхструктура, в частности сбалансированное двоичное дерево поиска (например, Красно-черное дерево , AVL-дерево, Splay Tree и т. д., если вы можете использовать stdlib, просто используйте std::multiset) или HashTable (в stdlib это std::unordered_multiset):

void preProcessing(dataStructure & ds, int * arr, int n){
    int sum = 0;
    int * toDelete = (int) malloc(n)
    for(int i = n-1; i >= 0; --i){
        sum += arr[i];
        toDelete[i] = sum; // Save items to delete later.
        tree.insert(sum);
    }

Таким образом, чтобы решить проблему, вам просто нужно пройти массив один раз:

// It considers that the deleted subarray could be empty
bool Solve(dataStructure & ds, int * arr, int n, int * toDelete){
    int sum = 0;
    bool solved = false; // true if a solution is found
    for(int i = 0 ; i < n; ++i){ 
        ds.erase(toDelete[i]); // deletes the actual sum up to i-th element from data structure, as it couldn't be part of the solution.
                               // It costs O(logN)(BBST) or O(1)(Hashtable)
        sum += arr[i];
        if(ds.find(sum)){// If sum is in ds, then there's a leftsum == rightsum
                         // It costs O(logN)(BBST) or O(1)(HashTable)
            solved = true;
            break;
        }
    }
    return solved;
}

Затем, если вы используетеBBST (сбалансированное бинарное дерево поиска) ваше решение будет O(NlogN), но если вы используете HashTable, ваше решение будет в среднем O(N).Я бы этого не реализовал, так что, возможно, есть ошибка, но я пытаюсь объяснить основную идею.