配列からペアを出力するコードをO(n)で実装したい

Question

昇順にソート済みで全ての要素が異なる配列から、与えられた和の値になるペアを全て出力するコードを書きたいです。
O(n)で実装したいのですが、以下のコードだと最大でも1つしかペアを出力できません。改善案、あるいは他のアルゴリズムがあれば教えていただきたいです。

int main(void)
{
    int i=0,j=4,sum;
    int x[5]={1,3,4,6,10};

    scanf("%d",&sum);

    for(i=0; i<5; ++i){
        printf("%d ",x[i]);
    }

    printf("\n");

    while(x[i]+x[j]<sum){
        ++i;
    }

    while(x[i]+x[j]>sum){
        --j;
    }

    if(x[i]+x[j]==sum){
        printf("(%d,%d)",x[i],x[j]);
    }
}

Comments

[LouiS0616]

値の取り得る範囲に制約はありますか？

[Hinomae]

情報漏れがありすみません。
配列の要素数、その値ともに任意の正の整数で制約はありません。

Answer 1

既存のロジックを繰り返すようにすれば良いのかなと思います。

i = 0;
while(i < j) {
    while(x[i]+x[j]<sum){
        ++i;
    }
    while(x[i]+x[j]>sum){
        --j;
    }

    if(x[i]+x[j]==sum){
        printf("(%d,%d)",x[i],x[j]);
        ++i;  // これが無いと無限ループするので注意
    }
}

追記: ループ部は次の方が良いかも。

while(1) {
    ...
    if(i >= j) { break; }
    printf(...);
}

あとは目的のペアが存在しないときなども考慮した方が良いですね。

参考

配列の要素数、その値ともに任意の正の整数で制約はありません。

もし取り得る値に制約があったなら、こういう解き方もできました。

// O(n)で値の逆引きを作る
// x_set[a] == 1 ならば、xはどこかにaを持っている
int x_set[10] = {0};
for(int i = 0; i < 5; ++i) {
    x_set[x[i]] = 1;
}
    
// O(n)で巡回
for(int i = 0; i < 5; ++i) {
    // これが無いと (a, b) と (b, a) の両方が表示されてしまう
    if(sum / 2 < x[i]) {
        break;
    }
        
    // x[i]=a,a+b=sumのとき、xはb=sum-x[i]を要素に持つか？
    if(x_set[sum-x[i]] == 1) {
        printf("(%d,%d)", x[i], sum-x[i]);
    }
}

実際には上限が分からなくても（当然C言語で表現できる範囲ならば）同じような解き方はできます。
ハッシュセットが提供されている言語なら楽なんですが。

Comments

[Hinomae]

回答ありがとうございます。

大きさnの配列x[n]でこの既存のロジックを繰り返した場合、オーダーはO(n)で収まりますか？
while(i < j)ループで最悪n/2回、その中のwhileループがO(n)(nを用いた正確な回数はちょっとわからなさそうです)になると考えると全体はO(n^2)になるのかな、と思ったのですがいかがでしょうか。

while文を付加すると上記のようになってしまうのでは？と思い投稿したのですが…

[LouiS0616]

while文は確かに二重になりますが、iとjの変化に着目すれば要素数分しか処理が走らないとの認識です。

[Hinomae]

確かにそうですね。
丁寧に回答ありがとうございました！