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

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

思路：首先应该注意标题中的关键字，输入的数组已经排序了，也就是说前面是小的数字，后面是大的数字。

自己代码：（从头开始遍历，会超时）

 vector<int> twoSum(vector<int>& numbers, int target) {

         int n = numbers.size();

         vector<int>index;

         for(int i = ; i < n - ; i++){

             for(int j = i + ; j < n; j++){

                 if(numbers[i] + numbers[j] == target){

                     index.push_back(i+);

                     index.push_back(j+);

                 }

             }

         }

         return index;

     }

优秀代码：(3ms)

 vector<int> twoSum(vector<int>& numbers, int target) {

         int m = , n = numbers.size() - ;

         while(m < n){

             if(numbers[m] + numbers[n] < target)

                 m++;

             else if(numbers[m] + numbers[n] > target)

                 n--;

             else

                 return vector<int>{m + , n + };//这里可以直接返回vector，{}表示赋值初始化

         }

     }

巴特西

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

最新文章

热门文章