LeetCode 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

题目标签：Array, Two Pointers

　　题目给了我们一个array，和一个 target， array 是递增排列的，让我们找到两个数字之和等于 target。这里要返回的是它们的index，不过是从1开始的。

　　利用two pointers，一个left = 0，一个 right = numbers.length - 1，因为array 是递增排列的，所以当 left 数字 + right 数字大于 target 的话，说明之和太大了，需要更小的数字，所以把 right-- 来拿到更小的数字；

　　当left 数字 + right 数字小于 target 的话，说明之和太小了，需要更大的数字，所以要把 left++ 来拿到更大的数字；

　　当 left 数字 + right 数字等于target 的话，直接返回 index + 1。

Java Solution:

Runtime beats 44.34%

完成日期：04/06/2017

关键词：Array, Two Pointers

关键点：了解两数之和与 target 的比较下两个指针该如何移动，建立在递增array的情况下

 public class Solution

 {

     public int[] twoSum(int[] numbers, int target)

     {

         int left = 0, right = numbers.length-1;

         int res[] = new int[2];

         while(left < right)

         {

             // find two numbers

             if((numbers[left] + numbers[right]) == target)

             {

                 res[0] = left + 1;

                 res[1] = right + 1;

                 break;

             }

             else if((numbers[left] + numbers[right]) > target) // if greater, right moves to left 1 place

                 right--;

             else // if less, left moves to right 1 place

                 left++;

         }

         return res;

     }

 }

参考资料：

http://www.cnblogs.com/ganganloveu/p/4198968.html

LeetCode 算法题目列表 - LeetCode Algorithms Questions List

巴特西

LeetCode 167. Two Sum II - Input array is sorted （两数之和之二 - 输入的是有序数组）

最新文章

热门文章