leetcode 167 Two Sum II - Input

题目描述：

题目截图.png

思路：

• 看到是升序的，就想可以使用二分查找，嗯，然后就使用了二分查找，可以通过，但是效率不高(122s)。

  var twoSum = function(numbers, target) {
  var result = [];
  var len = 0;
  while(numbers[len] <= target){
    len++
  }
  for(var i = 0; i <= len; i++){
      var s = numbers[i];
      var j = search(target-s, i+1, len, numbers);
      if(j != -1){
          result.push(i+1);
          result.push(j+1);
          return result;
      }
    }
  };
  
  var search = function(target, start, end, numbers){
  
  while(start <= end){
      var mid = parseInt((start+end)/2);
      if(numbers[mid] == target){
          return mid;
      }else if(numbers[mid] > target){
          end = mid-1;
      }else{
          start = mid+1;
      }
    }
  return -1;
  }
  

• 看了大家的解题思路原来更简单，从左右两侧使用两个指针进行循环判断就可以了。（95s）

  /**
   * @param {number[]} numbers
   * @param {number} target
   * @return {number[]}
   */
  var twoSum = function(numbers, target) {
      var result = [];
      var left = 0;
      var right = numbers.length-1;
  
      while(left <= right){
         if(numbers[left] + numbers[right] == target){
            result.push(left+1);
            result.push(right+1);
            return result;
        }else if(numbers[left] + numbers[right] > target){
            right--;
        }else{
            left++;
        }
      }
  };