2 つの和を効率的に解く II - 入力配列がソートされる-jsチュートリアル-php.cn

2 つの和を効率的に解く II - 入力配列がソートされる

Susan Sarandon

リリース： 2024-12-31 09:10:14

オリジナル

273 人が閲覧しました

Efficiently Solving Two Sum II - Input Array Is Sorted

「Two Sum II - 入力配列がソートされる」問題は、配列とポインター操作の理解をテストする古典的なコーディングの課題です。また、エレガントかつ効率的なソリューションを紹介する絶好の機会でもあります。問題を深く掘り下げて、それを解決するための最適なアプローチを詳しく見てみましょう。

LeetCode の問題へのリンク

問題提起

非降順でソートされた整数のインデックスが 1 の配列が与えられた場合、目標は、その合計が指定されたターゲットに等しくなる 2 つの数値を見つけることです。これら 2 つの数値のインデックスを配列 [index1, Index2] として返す必要があります。ここで、1

制約

配列番号は非降順でソートされます。
解決策は 1 つだけです。
同じ要素を 2 回使用することはできません。
入力配列の長さの範囲は 2 ～ 30,000 です。
配列の値の範囲は -1000 ～ 1000 です。

入力と出力の例

入力: 数値 = [2,7,11,15]、ターゲット = 9

出力: [1, 2]
入力: 数値 = [2,3,4]、ターゲット = 6

出力: [1, 3]
入力: 数値 = [-1,0]、ターゲット = -1

出力: [1, 2]

アプローチ: 2 つの指針

問題の制約 (ソートされた配列と単一の解) により、この問題は 2 ポインター手法の完璧な候補になります。その理由は次のとおりです:

効率: 2 つのポインターを使用すると、配列を 1 回のパスで走査できます (時間計算量は O(n))。
定数スペース: 一定の追加スペースという問題の要件を遵守し、補助データ構造を回避します。

実装

以下は、2 ポインターアプローチの JavaScript 実装です。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const length = nums.length;
    let rightPointer = length - 1;
    let leftPointer = 0;

    while (leftPointer < rightPointer) {
        if (nums[leftPointer] + nums[rightPointer] === target) {
            return [leftPointer + 1, rightPointer + 1];
        }
        if (nums[leftPointer] + nums[rightPointer] > target) {
            rightPointer--;
        } else {
            leftPointer++;
        }
    }
};

ログイン後にコピー

仕組み

2 つのポインターを初期化します:
- leftPointer は配列の先頭から始まります。
- rightPointer は配列の最後から始まります。
会うまで繰り返す:
- leftPointer と rightPointer の要素の合計を計算します。
- 合計がターゲットと一致する場合、1 から始まるインデックスの位置を返します。
- 合計がターゲットより大きい場合は、rightPointer をデクリメントして合計を減らします。
- 合計がターゲットより小さい場合は、leftPointer をインクリメントして合計を増やします。
インデックスを返します:
- 正しいペアが見つかると、ループは終了し、インデックスを返します。