O（n）の2つのスタックの整数を比較する方法は？

Question

私は2つのスタックs1とs2を持っています。 s1は負の整数を含み、s2は正の整数を含む。両方のStacksはすでに最低値（下）から最高値（上）までソートされています。 x1とx2はs1とs2の整数です。私は[x1 + x2 =与えられた整数i]かどうかを見るために両方のスタックをチェックしたいと思います。 O（n）でこれを行うための最良の方法（または方法）は何ですか？

更新：x1とx2は

integers..sorryあるアップデート2：メソッドはブール値を返し、これらのパラメータを持っているでしょう：

boolean method(Stack s1, Stack s2, int i) 

方法は、任意の整数X1場合はtrueを返しますs1 + s2の任意の整数x2 = i

Answer 1

s1の任意の数+ s2の任意の数が所定の整数iであると仮定します。

もしそうなら、

1. は、両方のスタック
2. のトップをオフにポップ
3. iは
   1. はい、彼ら等しいか、それらを追加 - >あなたが
4. です行われますそれは私よりも大きい？
   1. YES - 、>その後、正の数は何の対応を持つことはできません - >そして、負の数は、何の対応を持つことはできませんそれを捨てる、S1から次の負の数をオフにポップ、後藤2
   2. NO EDIT
      - （返答がないスタックが空の場合はいつでも、あなたが行われている）後藤2

、S2から次の正の数をオフにポップ、それを捨てます：あなたのソート順に基づいて私はステップ4で間違っていると思う - しかし、この基本的なアイデアは閉鎖するべきですe。