Sign in

[Java][TwoPoint][LeetCode] Two Sum II — Input array is sorted #167

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

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

It’s a two reverse traversal problem. I used tow points to solved. We know the Two Sum question. That solution is HashMap. But, HashMap can’t know the index position directly. So, this problem I used two points.
The right point start from 0 and move to left. The left point start from length-1 and move to right. If sum of right point and left point larger than target. It’s mean value of left point is too large. Thus, I need to move left point to right. Opposite, if there is lesser than target. I need to move right point to left. Until I get target.

使用雙指針,並以相反方向進行歷遍。若雙指針的和大於target,則表示大數需要變小,所以要將最右側的指針往左移,若雙指針的和小於target,則表示小數需要加大,所以要將最左側的指針右移,直到找到target,就把位置+1輸出。