167. 两数之和 II - 输入有序数组

[xuanWangisAlibaba19960403]

167. 两数之和 II - 输入有序数组

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

解题代码

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
  const dict = new Map();
  for (let i = 0; i < len; i++) {
    const number = target - numbers[i];
    if (dict.has(number)) {
      return [dict.get(number), i + 1];
    } else {
      dict.set(numbers[i], i + 1);
    }
  }
  return [-1, -1];
};

var twoSum = function (numbers, target) {
  let left = 0, right = numbers.length - 1;
  while (left < right) {
    let sum = numbers[left] + numbers[right];
    if (sum === target) {
      return [left + 1, right + 1];
    } else if (sum > target) {
      right--;
    } else {
      left++;
    }
  }
  return [-1, -1];
};

解体思路

首先我第一个想到的是计算差值然后在map中查找差值是否存在，如果不存在就把当前的num放到map中
时间(n) 空间(n) 
第二个方法双指针法，夹逼直到找到结果或者没有结果
时间(n) 空间(1)

解题代码

var twoSum = function (numbers, target) {
  const len = numbers.length;
  for (let i = 0; i < len; i++) {
    let left = i + 1, right = len - 1;
    while (left <= right) {
      const mid = left + right >> 1;
      if (numbers[mid] === target - numbers[i]) {
        return [i + 1, mid + 1];
      } else if (numbers[mid] > target - numbers[i]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
  }
  return [-1, -1];
}

解题思路

题干中说到数组按升序排列，并且是找到和为target的值，如果固定一个值为当前索引，
那么另一个可以通过二分查找去寻找，最后找到找到结果或者没有结果
本身二分查找的时间为T1(n) = O(logn)
循环数组的复杂度为T2(n) = O(n)
所以总的时间复杂度为T = T1(n) * T2(n) = O(logN) * O(n) = O(nlogn)