o（n）の配列の左辺の合計が

Question

であるかどうかを確認します。数字の配列（整数）が与えられ、右辺の数値の和が等しい場合は要素を返す必要があります彼の左のサイズの数字の合計はo（n）です。私は私のコードを取り付け9

1 + 2 + 2 = 5、3 + 2 = 5

ため

例えば配列{1,2,2,9,3,2} は、プログラムが印刷する必要なくそれは複雑さではありません。 ご協力いただきありがとうございます。

ありがとうございました。観察と

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はもはや満たされていない）：これはO(n)で動作するはず

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

、あなたは配列をソートする必要はありません。

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

}