[LeetCode] 167. Two Sum II - Input array is sorted

轉自LeetCode

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

<Solution>
Two Sum 的衍生題，這次給的 array 是排序過的

那最直接的想法是

• 綁訂一個值，然後歷遍找是否有答案

• 如果當下沒有答案，重複這個過程，直到找到答案

時間複雜度是O(n^2)，code如下

C++

還有一個O(n)的解法，想法如下

• 用左右指標來找答案

• 當和比目標值小，左指標往右。當和比目標值大，右指標往左

code如下(參考資料)

C++


Java


Kotlin

或者依然使用和 1. Two Sum 的想法也是可以

kotlin