objective-c - 配列/リスト内の3つの数値の合計が特定の数値と一致するかどうかを確認するObjectiveCコードを作成するにはどうすればよいですか？

Question

重複の可能性：
合計が指定された数に最も近い配列内の3つの要素を検索する

配列/リスト内の3つの数値の合計が特定の数値と一致するかどうかを確認するObjectiveCコードを作成するにはどうすればよいですか？

Answer 1

ステップ 1: 並べ替え、O(nlgn)

ステップ 2: すべての数値、たとえば A を繰り返します (これは O(n) のコストがかかります)。次に、任意の 2 つの数値の合計が、指定された数値から A を引いた値に等しいかどうかを確認します (これは、O(n) のコストがかかる古典的な問題です)。

総複雑度: O(n^2)

Answer 2

ここに別の方法があります

X、Y、Z は配列のインデックスであり、P には Number が指定されます。

条件が X+Y=P の場合、配列を並べ替えてから、各要素を選択し、残りの配列で PY を検索します。検索が成功した場合、それ以外の場合は False を返します。

したがって、検索にはlog（n）時間（バイナリ検索）がかかるため、n要素の場合、O（nlog（n））時間かかります。

今、私たちの条件は X+Y+Z=P です X+Y=PZ と推論します

Now Pick a number Z and calculate P-Z and let it be R . 
Now the problem is deduce to X+Y=R .So time complexity is O(nlog(n))
Since R varies n times for n picks in array so complexity is O((N^2)log(n))) .

Answer 3

これはPythonでのブルートフォースソリューションであり、その簡潔さだけで価値があり、効率性はまったくありません。

import itertools
def anyThreeEqualTo(list, value):
    return any([sum(c) == value for c in itertools.combinations(list, 3)])

別のアイデア:

import itertools
def anyThreeEqualTo(list, value):
    for c in itertools.combinations(list, 3)])
        if sum(c) == value:
            return True
    return False

これらのソリューションは、目的の合計を持つものが見つかるまで、各トリプレットを順番に試します。