整数が整数の和の1つであるかどうかを調べる効率的な方法

Question

これは学校の割り当てですが、プログラムは「最大のパフォーマンスで実装されている」という要件でした。メモリがスピードを上回るかどうかなど知っているだろう。しかし、私が探しているのは、入力データに対してスマートな操作を行うことで問題を解決する "トリッキーな"方法があるかどうかである。

だから、ここで問題があります：A.

の任意の2つの 以降の要素の和に等しいBでこのような整数がある場合は1を返す関数を、書く、あなたは二つの配列、AとBを持って考えます

以下は私の書き上げです。 Hashmap<Integer>を使用しなかったことに注意してください。なぜなら、スピードアップに必要なメモリは、O（n * m）のスピードでO（n *）の代わりに最悪の場合のスピードで十分に不利なものだと考えていたからです。

public static int arrayContainsSum(int[] a, int[] b) 
{ 
    int offsetA = a.length - 1; 
    int offsetB = offsetA; 
    int index = b.length - 1; 
    int result = 0; 
    int tested; 

    while (index >= 0) 
    { 
     if (offsetA > 0) a[offsetA] += a[--offsetA]; 
     else if (offsetA == 0) // This has a danger of overflowing the int 
      a[offsetA--] = multiply(a); 
     tested = b[index]; 
     if ((offsetA < 0 && tested != 0 && a[0] % tested != 0) || 
      offsetB == 0) 
     { 
      // No point to test this element as it doesn't 
      //divide the product of sums 
      offsetB = a.length - 1; 
      index--; 
     } 
     if (tested == a[offsetB--]) 
     { 
      result = 1; 
      break; 
     } 
    } 
    return result; 
} 

private static int multiply(int[] input) 
{ 
    int accumulator = input.length > 0 ? 1 : 0; 
    for (int i : input) 
     if (i != 0) accumulator *= i; 
    return accumulator; 
} 

私が心配していないことがいくつかあります：整数のオーバーフロー（乗算の結果として起こりうる）。私はarray.lengthがローカル変数からの読み込みと同じくらい速いと仮定しました。

しかし、私の質問はむしろ「分析的にこの問題を解決することはできませんでしたか？より良い効率を意味するでしょうか？

PS。この問題には、配列にユニークなメンバーしか含まれていないことは言及されていません。私はまた、aをソートすることによって最適化することが可能であると考えているので、がaの最小要素より小さく、次にaの最大要素よりも小さい場合は、いくつかのルックアップを保存します。これもまた複雑さが増し、恐らく完全に正当化されないであろう。

Answer 1

public static int arrayContainsSum(int[] a, int[] b) { 
    final Set<Integer> sums = new HashSet<Integer>(); 
    for (int i = 0; i < a.length - 1; i++) sums.add(a[i] + a[i+1]); 
    for (int x : b) if (sums.contains(x)) return 1; 
    return 0; 
} 

Answer 2

要素が100万を超え、1秒以上かかる場合を除き、速度は関係ありません。 Btwでは、100万個以上の要素の配列を作成する必要はありません。

7までのJavaバージョンには、基本的な設定操作さえありません。しかし、それらはGoogle Guavaライブラリで見つけることができます（そのコードは適切にテストされ、できるだけ効率的です）。

あなたは2組の20個の要素、aとb考えてみましょう - あなたが見つけたいその後1から100までのランダムで選択され、200

a = RandomInteger[{100}, 20] 
b = RandomInteger[{200}, 20] 

を何のa和の集合の要素後続の要素は、例えばb

ap = Table[Total[{a[[i]], a[[i + 1]]}], {i, 1, Length[a] - 1}] 
Intersection[ap, b] 

と交差：

{73,43,99,33,80,35,54,82,50,23,92,22,54,4,14,14,8,80,92,85} 
{121,139,158,158,51,176,65,84,76,172,73,148,71,128,55,134,4,32,183,134} 
{116,142,132,113,115,89,136,132,73,115,114,76,58,18,28,22,88,172,177} 
{73,76,172} 

Answer 3

不確かな場合は、ブルートフォースを使用してください。

もちろん、実行可能なソリューションを作成するタスクであれば、これでは不十分かもしれませんが、ソリューションを最適化する前に解決策が必要です。

val a = List (3, 9, 7, 4, 16)  
val b = List (29, 12, 21, 16, 18, 14) 

for (i <- (0 to a.length - 2); 
    j = i+1; 
    if b.exists (_ == a(i)+a(j))) yield (a(i), a(j), a(i)+a(j)) 

どのくらいの頻度で実行されますか？ 外側のループは、1から配列長さ-1（ここではリストです）を実行してi、jを生成します。

しかし、それはあなたがソート値によるBならば、あなたはBでバイナリ検索を行うことができ、全体アレイ、

を通じて常に走るBの。 2つの配列が与えられているので、HashMapはルールから許可されていないと思います。それ以外の場合、HashMapは高速です。