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

我会带着你远行 2022-06-16 01:50 147阅读 0赞

# 1.题目描述 #

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.  
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  
翻译：给一个排序好的数组，找出其中两个元素的和等于指定值。返回这两个元素的下标。假定一定有且只有一个解。

# 2.分析 #

两种方式：  
（1）从左边开始，对于每个元素x，使用二分查找元素target-x  
（2）从数组两端往中间搜索。  
left+right>target right–;left+right

# 3.代码 #

c++  
二分查找

int binaryS(vector<int>& numbers, int num, int start,int end) {
            int middle;
            while (start <= end) {
                middle = (start + end) >> 1;
                if (numbers[middle] > num)
                    end = middle - 1;
                else if (numbers[middle] < num)
                    start = middle + 1;
                else
                    return middle;
            }
            return -1;      
        }
        vector<int> twoSum(vector<int>& numbers, int target) {
            int i = 0;
            int j;
            int length = numbers.size();
            while (numbers[i] <= target) {
                j = binaryS(numbers, target - numbers[i], i+1, length - 1);
                if (j > 0)
                    break;
                else
                    ++i;
            }
            return vector<int>{i+1, j+1};
        }

第二种

vector<int> twoSum(vector<int>& numbers, int target) {
            int i = 0;
            int j = numbers.size() - 1;
            while (i < j) {
                if (numbers[i] + numbers[j] == target)
                    return vector<int>{i + 1, j + 1};
                else if (numbers[i] + numbers[j] > target)
                    --j;
                else
                    ++i;
            }
        }