Leetcode (167) -- sum of two numbers II - input ordered array

Leetcode（167）—— Sum of two numbers II - Input an ordered array

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] .

Tips ：

• $2$ <= numbers.length <= $3\ast 10^4$
• $-1000$ <= numbers[i] <= $1000$
• numbers Press Non decreasing order array
• $-1000$ <= target <= $1000$
• There is only one valid answer

Answer key

This problem can be used 「1. Sum of two numbers 」 Solution method , Use $O(n^2)$ Time complexity and $O(1)$ The space complexity is solved violently , Or with a hash table $O(n)$ Time complexity and $O(n)$ To solve the space complexity of . But both of them are for unordered arrays , It doesn't take advantage of the ordered nature of the input array . Using the ordered property of input array , We can get the solution with better time complexity and space complexity .

Method 1 ： Double pointer

Ideas

​​   Initially, two pointers point to the position of the first element and the position of the last element . Calculate the sum of two elements pointed to by two pointers at a time , And compare with the target value . If the sum of the two elements is equal to the target value , The only solution is found . If the sum of the two elements is less than the target value , Then move the left pointer to the right one bit . If the sum of the two elements is greater than the target value , Move the right pointer to the left by one bit . After moving the pointer , Repeat the above operation , Until you find the answer .

​​   The essence of using double pointers is Narrow the search . Then will the possible solutions be filtered out ？ The answer is no .
​​   prove ： hypothesis $\text{numbers}[i]+\text{numbers}[j]=\text{target}$ It's the only solution , among $0\le i<j\le \text{numbers}.\text{length}-1$. Initially, the two pointers point to the subscript $0$ And subscripts $\text{numbers}.\text{length}-1$, The left pointer points to a subscript less than or equal to $i$, The right pointer points to a subscript greater than or equal to $j$. Unless the left and right pointers are already in the subscript $i$ and $j$, Otherwise, the left pointer must reach the subscript first $i$ The position or right pointer reaches the subscript first $j$ The location of .

• Suppose the left pointer reaches the subscript first $i$ The location of , Then the right pointer is still subscript $j$ The right side of the ,$\text{numbers}[i]+\text{numbers}[j]>\text{target}$, Therefore, the right pointer must move to the left , The left pointer cannot be moved to $i$ The right side of the .
• Suppose the right pointer reaches the subscript first $j$ The location of , Then the left pointer is still subscript $i$ The left side of the ,$\text{numbers}[i]+\text{numbers}[j]<\text{target}$, Therefore, the left pointer must move to the right , The right pointer cannot move to $j$ The left side of the .

thus it can be seen , Throughout the movement , The left pointer cannot be moved to $i$ The right side of the , The right pointer cannot move to $j$ The left side of the , Therefore, possible solutions will not be filtered out . Because the question ensures that there is a unique answer , Therefore, the answer can be found by using double pointers .

Code implementation

class Solution {
    
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
    
        int size = numbers.size();
        vector<int> ans{
    1, 2};
        if(size == 2) return ans;
        int n = 0, m = size-1;  //  Double pointer , Reverse traversal 
        while(true){
    
            if(numbers[m] + numbers[n] > target) m--;
            else if(numbers[m] + numbers[n] < target) n++;
            else break;
        }
        ans[0] = n+1;
        ans[1] = m+1;
        return ans;
    }
};

Complexity analysis

Time complexity ：$O(n)$, among $n$ Is the length of the array . The maximum total number of times two pointers move is $n$ Time , That is, you can traverse the array at most , The worst case is that the two numbers to be found are adjacent .
Spatial complexity ：$O(1)$