2017-09-05 2 views
0

大企業でのインタビュー質問:どのように解決しますか?任意の整数から、期待した合計に合ったペアを見つけ、配列の結果をコレクションとして返します

任意の整数のリストが与えられれば、未知の期待合計に合計する整数のペアを見つける。配列の結果をコレクションに返します。

これは私がからスタートしなければならなかったものです:

class NumericalEntityProcessor { 

    List<Integer[]> pairsThatSumToX(List<Integer> input, Integer expectedSum) { 

    } 
} 

は解決方法の2です - しかし、私は

class NumericalEntityProcessor { 

    List<Integer[]> pairsThatSumToX(List<Integer> input, Integer expectedSum) { 

    int n = list.size() + 2; 
    int expectedSum = n * (n + 1)/2; 
    int expectedSquaredSum = n * (n + 1) * (2 * n + 1)/6; 
    int sum = 0; 
    int squaredSum = 0; 

    System.out.println("SIZE :::" + list.size()); 

    for (Object num : list) { 
     sum = sum + (int)num; 
     squaredSum = squaredSum + ((int)num * (int)num); 
    } 

    int xplusy = expectedSum - sum; 
    int xsquareplusysquare = expectedSquaredSum - squaredSum; 
    int twoxy = xplusy * xplusy - xsquareplusysquare; 
    int xminusy = (int) Math.sqrt(xsquareplusysquare - twoxy); 
    int x = (xplusy + xminusy)/2; 
    int y = (xplusy - xminusy)/2; 

    return new Integer[] { x, y }; 

    int sum = list.stream().map(Line::getLength).collect(Collectors.summingInt(i->i)); 
    } 
} 

あるいは、二

attempt- ...何かを逃しました
public class ArrayExample1 { 

    public static void main(String[] args) { 

     int[] number = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 

     List<Integer> list = convertIntArrayToList(number); 
     System.out.println("list : " + list); 

    } 

    private static List<Integer> convertIntArrayToList(int[] input) { 

     List<Integer> list = new ArrayList<>(); 
     for (int i : input) { 
      list.add(i); 
     } 
     return list; 
     IntSummaryStatistics stats = list.stream() 
        .collect(Collectors.summarizingInt(Line::getLength)); 
     IntSummaryStatistics stats = list.stream().flatMap(a->Arrays.stream(a)) 
        .collect(Collectors.summarizingInt(i->i)); 
     System.out.println(stats.getSum());  
     } 
    } 
} 

答えて

0
  1. リストをソート
  2. 現在の数値が合計場合注意、一つは参照番号の合計が目標反復後
  3. 未満である間、他のポインタを末尾に開始し
  4. 移動をデクリメント、頭部から始まりインクリメント二つのポインタを定義します合計によりソートする対象

を超えた場合、他のポインタ

  • 終了反復でターゲット
  • 手順3を繰り返し、このアルゴリズムは、O(Nログn)の時間複雑性を有します。反復部分はO(n)であり、全体の時間複雑性を決定する目的で無視される。

  • 関連する問題