35

質問: 正の整数の並べ替えられていない配列が与えられた場合、その配列から合計が特定の合計になる整数のペアを見つけることは可能ですか?

制約: これは、O(n) およびインプレース (配列、ハッシュマップなどの外部ストレージなし) で実行する必要があります (追加の変数/ポインターを使用できます)。

これが不可能な場合、同じことを証明できますか?

4

19 に答える 19

55

ソートされた配列がある場合、2 つのポインターを中央に移動することで、O(n) でそのようなペアを見つけることができます。

i = 0
j = n-1
while(i < j){
   if      (a[i] + a[j] == target) return (i, j);
   else if (a[i] + a[j] <  target) i += 1;
   else if (a[i] + a[j] >  target) j -= 1;
}
return NOT_FOUND;

数値のサイズに制限がある場合 (または、配列が最初から既にソートされている場合) は、ソートを O(N) にすることができます。それでも、log n ファクターは非常に小さいので、わざわざ削りたくありません。

証拠：

解が存在する場合(i*, j*)、一般性を失うことなく、それが にi到達i*する前jに到達するとしj*ます。とのj'間のすべてについて、それを外挿できることがわかっているため、アルゴリズムの後続のすべてのステップでは、j が到達(または等しい値)になるまで j が減少し、前に進んで「ミス」する機会が与えられないことがわかっています。解決。j*ja[j'] > a[j*]a[i] + a[j'] > a[i*] + a[j*] = targetj*i

反対方向の解釈も同様です。

于 2011-12-01T00:35:57.427 に答える
12

ソートされた配列で機能するO(N)時間と空間のソリューション:O(1)

Mあなたが求めている値にしましょう。2 つのポインターと を使用XしYます。X=0最初とY=N-1最後から始めます。合計を計算しsum = array[X] + array[Y]ます。の場合sum > MはデクリメントYし、そうでない場合はインクリメントしますX。ポインターが交差する場合、解は存在しません。

一般的な配列でこれを取得するためにその場で並べ替えることができますが、一般的にO(N)時間とO(1)空間の解決策があるかどうかはわかりません。

于 2011-12-01T00:35:44.903 に答える
3

@PengOneが述べたように、一般的なスキームでは不可能です。ただし、i/pデータにいくつかの制限を設ける場合。

  1. すべての要素はすべて+またはすべて-です。そうでない場合は、範囲（高、低）を認識して変更を加える必要があります。
  2. K、2つの整数の合計は、一般的な要素と比較してまばらです。
  3. i/p配列A[N]を破棄しても問題ありません。

ステップ1：SUM未満のすべての要素を配列の先頭に移動します。たとえば、Nパスでは、[0、K]に要素<= SUMが含まれるように、配列を[0、K]と[K、N-1]に分割しました。

ステップ2：境界（0からSUM）がわかっているので、基数ソートを使用できます。

ステップ3：A [K]で二分探索を使用します。1つの良い点は、相補的な要素を見つける必要がある場合、配列A[K]の半分を調べるだけでよいということです。したがって、A [k]では、A[0からK/ 2 + 1]を反復処理し、A[iからK]で二分探索を行う必要があります。

したがって、合計約 時間は、N + K + K / 2 lg（K）です。ここで、Kは、0からi / pA[N]の合計までの要素の数です。

注：@PengOneのアプローチを使用する場合は、Kでstep3を実行できます。したがって、合計時間はN + 2Kになり、これは間違いなくO（N）です。

追加のメモリは使用しませんが、i / p配列を破棄します。これも、最初から順序付けがなかったため、悪くはありません。

于 2011-12-04T14:48:50.530 に答える
3

これは、配列に数値が含まれている場合に可能であり、その上限は事前にわかっています。次に、カウントソートまたは基数ソート（o（n））を使用し、@PengOneが提案したアルゴリズムを使用します。

そうでなければ、O(n) ソリューションは考えられませんが、O(nlgn) ソリューションは次のように機能します。

まず、マージソートまたはクイックソート（インプレースの場合）を使用して配列をソートします。sum - array_element がこのソートされた配列にあるかどうかを調べます。そのために二分探索を使用できます。

So total time complexity: O(nlgn) + O(lgn) -> O(nlgn).
于 2011-12-04T10:48:08.893 に答える
2

次のサイトでは、ハッシュセットを使用して数値を確認し、指定された合計現在の数値をハッシュセットで検索する簡単なソリューションを提供してい ます http://www.dsalgo.com/UnsortedTwoSumToK.php

于 2013-01-30T13:39:53.743 に答える
2
  1. count sort を使用して、配列 O(n) をソートします。

  2. 配列の 0 番目のインデックスから始まる 2 つのポインターと、配列の終わりからのポインター (n-1) を取得します。

    低<=高になるまでループを実行します

    Sum = arr[low] + arr[high]  
if(sum == target)
       print low, high
if(sum < target)
       low++
if(sum > target)
       high--

    ステップ 2 から 10 には O(n) の時間がかかり、並べ替えのカウントには O(n) かかります。したがって、合計時間の複雑さは O(n) になります。

于 2016-08-01T10:09:43.707 に答える
2

まず、radix sortを使用して配列をソートします。それはあなたをO（kN）に戻します。次に、@PengOneが提案するように進みます。

于 2011-12-01T00:37:53.260 に答える
1

これは、重複エントリを考慮したソリューションです。JavaScript で書かれており、並べ替えられた配列と並べ替えられていない配列を使用して実行されます。ソリューションは O(n) 時間で実行されます。

var count_pairs_unsorted = function(_arr,x) {
  // setup variables
  var asc_arr = [];
  var len = _arr.length;
  if(!x) x = 0;
  var pairs = 0;
  var i = -1;
  var k = len-1;
  if(len<2) return pairs;
  // tally all the like numbers into buckets
  while(i<k) {
    asc_arr[_arr[i]]=-(~(asc_arr[_arr[i]]));
    asc_arr[_arr[k]]=-(~(asc_arr[_arr[k]]));
    i++;
    k--;
  }
  // odd amount of elements
  if(i==k) {
    asc_arr[_arr[k]]=-(~(asc_arr[_arr[k]]));
    k--;
  }
  // count all the pairs reducing tallies as you go
  while(i<len||k>-1){
    var y;
    if(i<len){
      y = x-_arr[i];
      if(asc_arr[y]!=undefined&&(asc_arr[y]+asc_arr[_arr[i]])>1) {
        if(_arr[i]==y) {
          var comb = 1;
          while(--asc_arr[_arr[i]] > 0) {pairs+=(comb++);}
        } else pairs+=asc_arr[_arr[i]]*asc_arr[y];
        asc_arr[y] = 0;
        asc_arr[_arr[i]] = 0;
      }

    }
    if(k>-1) {
      y = x-_arr[k];
      if(asc_arr[y]!=undefined&&(asc_arr[y]+asc_arr[_arr[k]])>1) {
        if(_arr[k]==y) {
          var comb = 1;
          while(--asc_arr[_arr[k]] > 0) {pairs+=(comb++);}
        } else pairs+=asc_arr[_arr[k]]*asc_arr[y];
        asc_arr[y] = 0;
        asc_arr[_arr[k]] = 0;
      }

    }
    i++;
    k--;
  }
  return pairs;
}

配列の両側から始めて、ゆっくりと内側に向かって進み、各数字が何回見つかったかを数えます。中間点に到達すると、すべての数字が集計され、ペアを数えながら両方のポインターを進めることができます。

ペアのみをカウントしますが、再加工することができます

  • ペアを見つける
  • ペア < x を見つける
  • ペアを見つける > x

楽しみ！

于 2013-03-29T14:37:24.897 に答える
0

Java では、これは配列の最大数に依存します。2 つの要素のインデックスを持つ int[] を返します。O(N)です。

  public static int[] twoSum(final int[] nums, int target) {
    int[] r = new int[2];
    r[0] = -1;
    r[1] = -1;
    int[] vIndex = new int[0Xffff];
    for (int i = 0; i < nums.length; i++) {
        int delta = 0Xfff;
        int gapIndex = target - nums[i] + delta;
        if (vIndex[gapIndex] != 0) {
            r[0] = vIndex[gapIndex];
            r[1] = i + 1;
            return r;
        } else {
            vIndex[nums[i] + delta] = i + 1;
        }
    }
    return r;
}
于 2016-02-07T07:45:01.853 に答える
0

これがPythonでの解決策です：

a = [9, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 9, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 2, 8, 9, 2, 2, 8,
     9, 2, 15, 11, 21, 8, 9, 12, 2, 8, 9, 2, 15, 11, 21, 7, 9, 2, 23, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 12, 9, 2, 15, 11, 21, 8, 9, 2, 2,
     8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 7.12, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9,
     2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 0.87, 78]
i = 0
j = len(a) - 1
my_sum = 8
finded_numbers = ()
iterations = 0
while(OK):
    iterations += 1
    if (i < j):
        i += 1
    if (i == j):
        if (i == 0):
            OK = False
            break
        i = 0
        j -= 1
    if (a[i] + a[j] == my_sum):
        finded_numbers = (a[i], a[j]) 
        OK = False
print finded_numbers
print iterations
于 2013-11-08T11:29:25.937 に答える
0

面接で同じ質問をされましたが、これは私が考えていたスキームです。負の数を許可するために改善する必要がありますが、必要なのはインデックスを変更することだけです。スペース的には良くありませんが、ここでの実行時間は O(N)+O(N)+O(N のサブセット) -> O(N) になると思います。私は間違っているかもしれません。

void find_sum(int *array_numbers, int x){
 int i, freq, n_numbers; 
 int array_freq[x+1]= {0}; // x + 1 as there could be 0’s as well
 if(array_numbers)
 {
  n_numbers = (int) sizeof(array_numbers);
  for(i=0; i<n_numbers;i++){ array_freq[array_numbers[i]]++; } //O(N) 
  for(i=0; i<n_numbers;i++) 
  { //O(N) 
   if ((array_freq[x-array_numbers[i]] > 0)&&(array_freq[array_numbers[i]] > 0)&&(array_numbers[i]!=(x/2)))
   { 
    freq = array_freq[x-array_numbers[i]] * array_freq[array_numbers[i]];
    printf(“-{%d,%d} %d times\n”,array_numbers[i],x-array_numbers[i],freq ); 
    // “-{3, 7} 6 times” if there’s 3 ‘7’s and 2 ‘3’s
    array_freq[array_numbers[i]]=0;
    array_freq[x-array_numbers[i]]=0; // doing this we don’t get them repeated
   }
  } // end loop
  if ((x%2)=0)
  {
   freq = array_freq[x/2];
   n_numbers=0;
   for(i=1; i<freq;i++)
   { //O([size-k subset])
    n_numbers+= (freq-i); 
   } 
   printf(“-{%d,%d} %d times\n”,x/2,x/2,n_numbers);
  }
  return;
 }else{
 return; // Incoming NULL array 
 printf(“nothing to do here, bad pointer\n”);
 }
}

批評家は大歓迎です。

于 2015-07-17T17:39:45.903 に答える
-1

可能であるとは限りません。与えられた合計はどのように選択されますか?

例: ソートされていない整数の配列

2, 6, 4, 8, 12, 10

与えられた合計:

7

??

于 2011-12-01T22:22:47.440 に答える