[sum of two numbers] 169 sum of two numbers II - enter an ordered array

One 、 subject

I'll give you a subscript from 1 The starting array of integers numbers , The array has been pressed Non decreasing order , Please find out from the array that the sum satisfying the addition is equal to the target number target Two numbers of . Let these two numbers be numbers[index1] and numbers[index2] , be 1 <= index1 < index2 <= numbers.length .

In length 2 Array of integers for [index1, index2] Returns the subscript of these two integers in the form of index1 and index2.

You can assume that each input Only corresponding to the only answer , And you Can not be Reuse the same elements .

The solution you design must use only constant level extra space .

Example 1：

Input ：numbers = [2,7,11,15], target = 9
Output ：[1,2]
explain ：2 And 7 The sum is equal to the number of targets 9 . therefore index1 = 1, index2 = 2 . return [1, 2] .
Example 2：

Input ：numbers = [2,3,4], target = 6
Output ：[1,3]
explain ：2 And 4 The sum is equal to the number of targets 6 . therefore index1 = 1, index2 = 3 . return [1, 3] .
Example 3：

Input ：numbers = [-1,0], target = -1
Output ：[1,2]
explain ：-1 And 0 The sum is equal to the number of targets -1 . therefore index1 = 1, index2 = 2 . return [1, 2] .

Two 、 Answer key

This problem is to traverse an array , And find two elements , It's not an interval , And the array is ordered , Therefore, the double pointer method can be used .

• First initialize the double pointer , Point to the smallest position and the largest position respectively , The minimum position pointer traverses to the right , The maximum position pointer traverses to the left .
• In the process of traversing , There are three situations （1） Sum of two numbers > The goal is ： The maximum position pointer moves to the left ;2） Sum of two numbers < The goal is ： The minimum position pointer moves to the right ;3） Sum of two numbers = The goal is ： Successfully found

Be careful ： In the opposite direction, pay attention to the boundary conditions , Here are two pointers pointing to the same position

3、 ... and 、 Code

class Solution {
    
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
    
       int s = 0;
       int f = numbers.size()-1;

       while(s!=f){
    
           if((numbers[s] + numbers[f])==target) break;
           else if((numbers[s] + numbers[f])>target) f--;
           else s++;
       }
       return vector<int> {
    s+1,f+1};
    }
};