# LeetCode Easy 167. Two Sum II - Input array is sorted

tags: leetcode

問題

• Explore
• Problems

アイデア

既に昇順に整列した整数の配列を与えられた時，足すとある目的の数になるような2つの数を探せという問題．ただし，同じ要素を2回使ってはいけないのと，1-indexedなことに注意．

有名なTwo Sumを改題したもので，整列されているので，より効率が良いように問題を解けるはずです．

解法

もし整列されていない場合は連想配列を使うことで$O(N)$で問題を解くことが可能です．

しかし，ここでは整列されていることを利用して探索する範囲の左端をleft，右端をrightとします．常にnumbers[left] <= numbers[right]なのでleft == rightとなるまで両端の要素の和をtargetと比べます．

• 和がtargetとなるときはこのときのindexを1-indexedで返します
• 和がtargetより小さい時は左端を右にずらして，両端の和を大きくしようとします
• 我がtargetより大きい時は右端を左にずらして，両端の和を小さくしようとします

計算量

与えられる配列の長さをNとします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

連想配列を使うときよりも空間計算量が効率的です．

C++

class Solution {
public:
  vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0, right = numbers.size() - 1;
    while (left != right) {
      if (numbers[left] + numbers[right] == target)
        return {left+1, right+1};
      else if (numbers[left] + numbers[right] < target)
        left++;
      else
        right--;
    }
    return {};
  }
};