Проверьте, равна ли сумма левой части массива правой стороне массива в o (n)

Question

Мне был задан массив чисел (целое число), и мне нужно вернуть элемент, если сумма чисел в его правой части равна сумма чисел в его левом размере в o (n).

Например массив {1,2,2,9,3,2} программа должна напечатать 9, потому что 1 + 2 + 2 = 5 и 3 + 2 = 5

Я приложил свой код, но это не о (n) сложность. оцените вашу помощь.

Спасибо.

public class Program { 
    public static void checkIfEqualOption1(int[] arr){ 
     int sumRight = 0; 
     int sumLeft=0; 
     //sumRight+=numbers[0]; 
     for (int i=0; i < arr.length; i++){ 
      if (i>0){ 
       sumRight+=arr[i-1]; 
       for (int j=i+1; j<arr.length; j++){ 
        sumLeft+=arr[j]; 
       } 
       if (sumRight==sumLeft){ 
        System.out.println("\nFound = "+arr[i]); 
        break; 
       } 
      } 
     } 

    } 

    public static void print(int[] arr){ 
     for (int i=0; i < arr.length; i++){ 
      System.out.print(arr[i] + " "); 
     } 
    } 
    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     System.out.println("Hi"); 
     int[] numbers = {1,2,2,9,3,2}; 
     System.out.println("Array numbers:"); 
     for (int i=0; i < numbers.length; i++){ 
      System.out.print(numbers[i] + " "); 
     } 
     System.out.println("\n"); 
     checkIfEqualOption1(numbers); 
    } 
} 

Answer 1

Начните с наблюдения, что для каждого i

arraySum(0, i) + arraySum(i+1, n) == arrayTotal 

так

arraySum(i+1, n) == arrayTotal - arraySum(0, i); 
^^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^ 
Sum on the right     Sum on the left 

Вычисляется arrayTotal в первом проходе; затем пройдите по массиву слева, вычисляя частичную сумму. Стоп, как только вы достигнете позиции, где

partialSum == arrayTotal - partialSum 

Answer 2

Я пришел к этому решению, который вычисляет обе суммы с шагом от левых и правых позиций (posFromLeft и posFromRight в коде ниже), пока позиции не имеют «пересекла» друг друга (posFromRight > posFromLeft не довольствуясь больше):

public class Program { 

public static void checkIfEqualOption1(int[] arr){ 
    int sumRight = 0; 
    int sumLeft=0; 
    int arrayLength=arr.length; 
    for (int posFromLeft=0; posFromLeft < arrayLength; posFromLeft++){ 
     int posFromRight=arrayLength-posFromLeft-1; 
     if (posFromRight > posFromLeft){ 

     sumRight+=arr[posFromRight]; 
     sumLeft+=arr[posFromLeft]; 
     } 
    } 
System.out.println("right sum: "+sumRight); 
System.out.println("left sum: "+sumLeft); 
} 


public static void main(String[] args) { 


    int[] numbers = {1,2,2,9,3}; 
    System.out.println("Array numbers:"); 
    for (int i=0; i < numbers.length; i++){ 
     System.out.print(numbers[i] + " "); 
    } 

    checkIfEqualOption1(numbers); 
} 
} 

Answer 3

Это должно работать в O(n), вам не нужно сортировать массив:

public class Program { 

    public static void checkIfEqualOption1(int[] arr){ 

     int sumTotal=0; 
     for (int i=0; i < arr.length; i++){ // O(arr.length) 
      sumTotal += arr[i]; 
     } 

     int sumRight = 0; 
     int sumLeft=0; 
     for (int i=1; i < arr.length-1; i++){ // O(arr.length) 
      sumLeft += arr[i-1]; 
      sumRight = sumTotal - arr[i] - sumLeft; 
      if (sumRight == sumLeft){ 
       System.out.println("\nFound = "+arr[i]); 
       break; 
      } 
     } 
    } 


    public static void main(String[] args) { 

    int[] numbers = {1,2,2,9,3,2}; 
    System.out.println("Array numbers:"); 
    for (int i=0; i < numbers.length; i++){ 
      System.out.print(numbers[i] + " "); 
    } 
    System.out.println("\n"); 
    checkIfEqualOption1(numbers); 
    } 

} 

Это выходы:

Array numbers: 
1 2 2 9 3 2 


Found = 9 

Answer 4

я написал ниже код, чтобы проверить равенство суммы элементов массива и LHS RHS. getMidIndex() вернет индекс массива, где нашел равенство ....

public class Concepts { 

public static int getMidIndex(int[] elements) throws Exception { 
    int endIndex = elements.length - 1; 
    int startIndex = 0, sumL = 0, sumR = 0; 

    while (true) { 
     if (sumL > sumR) 
      sumR += elements[endIndex--]; 
     else 
      sumL += elements[startIndex++]; 
     System.out.println("StartIndex: " + startIndex + " Endindex: " + endIndex + " SumLeft: " + sumL 
       + " SumRight: " + sumR); 
     if (sumL == sumR) 
      break; 
     if (startIndex > endIndex) { 
      System.out.println("Invalid Array"); 
      break; 
     } 
    } 
    return endIndex; 
} 

public static void main(String[] args) throws Exception { 
    int[] array = { 1, 2, 2, 9, 3, 2 }; 
    int midVal = getMidIndex(array); 
    System.out.println("Mid index: " + midVal + " Value: " + array[midVal]); 
} 

}