关于算法:LeetCodeGolang-167-两数之和-II-输入有序数组

题目：

给你一个下标从 1 开始的整数数组 numbers，该数组已按非递加顺序排列，请你从数组中找出满足相加之和等于指标数 target 的两个数。如果设这两个数别离是 numbers[index1] 和 numbers[index2]，则 1 <= index1 < index2 <= numbers.length。

以长度为 2 的整数数组 [index1, index2] 的模式返回这两个整数的下标 index1 和 index2。

你能够假如每个输出 只对应惟一的答案，而且你 不能够 重复使用雷同的元素。

你所设计的解决方案必须只应用常量级的额定空间。

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers 按 非递加程序 排列
• -1000 <= target <= 1000
• 仅存在一个无效答案

题解：

能够应用 对撞指针 的办法，先贴代码（Go）：

func twoSum(numbers []int, target int) []int {l, r := 0, len(numbers)-1
   for l < r {sum := numbers[l] + numbers[r]
      if sum == target {return []int{l + 1, r + 1}
      } else if sum > target {r--} else {l++}
   }
   return nil
}

留神到题目中原始数组是升序的，所以咱们 l 和r别离从数组头和数组尾向两头遍历。

• 如果 numbers[l] + numbers[r] 的值大于 target 时，惟一放大的办法就是左移r。
• 如果 numbers[l] + numbers[r] 的值小于 target 时，惟一增大的办法就是右移 l。
  题目保障 仅存在一个无效答案，所以肯定会在遍历中找到适宜答案。

复杂度剖析：

• 工夫复杂度：O(n)，其中 n 是数组的长度。两个指针挪动的总次数最多为 n 次。
• 空间复杂度：O(1)。