# 前言

利用 LeetCode 來磨練演算法

# 題目連結

Two Sum II - Input Array Is Sorted - LeetCode

# 解題思路

# 暴力解

跑雙重回圈，每一個 index 都跟整個 array loop 過一次以確認是否相加可以得到 target，這樣時間複雜度為 N 的平方

# two pointers

由於 $numbers 是一個 sorted array, 由小至大, 所以可以使用 two pointers 來解

首先定義 $left 以及 $right, 並將其相加得到一個 $sum, 如果 $sum 等同 $target, 直接破案拿到 $left 跟 $right 的位置

如果 $sum 小於 $target, 代表 $left 可以往右移一格, 因為 $numbers 是有序的, 所以當前 $left 的下一個數勢必為此 array 中僅大於當前 $left 的數, 因此由此數來替換當前 $left 可取得下一個僅大於當前 $sum 的由兩個數相加的 $sum, 並用他再來跟 $target 比較一次

如果 $sum > $target, 原理同上, 則移動 $right 往左推, 取得下一個僅小於當前 $right 的數 此法時間複雜度為 O(n), 空間複雜度為 O(1) (不管 n 是多少, 都只維護 $left, $right, $sum)

# 解題程式碼

<?php
class Solution {

  /**
   * @param Integer[] $numbers
   * @param Integer $target
   * @return Integer[]
   */
  function twoSum($numbers, $target) {
      $left = 0;
      $right = count($numbers) - 1;

      while ($left < $right) {
          $sum = $numbers[$left] + $numbers[$right];

          if ($sum === $target) {
              return [$left+1, $right+1];
          } elseif ($sum > $target) {
              $right--;
          } else {
              $left++;
          }
      }

  }
}