通过删除子数组使数组左右两边的和相等 [英] Make sums of left and right sides of array equal by removing subarray

问题描述

C程序，该程序查找要删除的子数组的开始和结束索引，以使给定数组的左侧和右侧的总和相等.如果无法打印-1.我需要它可用于任何阵列，这仅用于测试.这是找到平衡的代码.

C program that finds starting and ending indexes of subarray to remove to make given array have equal sums of left and right side. If its impossible print -1. I need it to work for any array, this is just for testing. Heres a code that finds equilibrium.

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

推荐答案

通常情况下，您可以在 O(NlogN)或 O(N)中解决此问题).

You could solve this problem in O(NlogN) or O(N)(in average case).

首先，您需要进行预处理，将所有总和从右到左保存在数据结构中，尤其是平衡的二进制搜索树(例如 HashTable (在 stdlib 它是 std :: unordered_multiset ):

First, you need to make a pre-processing, saving all the sums from right to left in a data structure, specifically a balanced binary search tree(e.g. Red Black tree, AVL Tree, Splay Tree, etc, if you could use stdlib, just use std::multiset) or a HashTable(in stdlib it's 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);
    }

因此，要解决问题，您只需要遍历数组一次即可:

So to solve problem you just need to traverse the array one time:

// 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)平均.我不会实现它，所以也许有一个错误，但是我尝试解释主要思想.

Then, if you use a BBST(Balanced Binary Search Tree) your solution would be O(NlogN), but, if you use HashTable, your solution would be O(N) on average. I wouldn't implemented it, so maybe there's a bug, but I try to explain the main idea.

这篇关于通过删除子数组使数组左右两边的和相等的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！