题目描述

Two Sum

给出一个整数数组，返回数组中两个元素满足相加等于一个目标数字的索引。
可以限定只存在唯一解，且不会使用相同的元素两次(即数组中不存在两个相同的元素)

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

javascript:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {

}

From leetcode No.1 Easy (opens new window)

解法

点击查看

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
  let left = 0
  let right = nums.length -1
  const sorted_nums = Array.from(nums)
  sorted_nums.sort((a,b)=>a-b)
  while(left < right){
    if(sorted_nums[left] + sorted_nums[right] === target)
      break;
    else if(sorted_nums[left] + sorted_nums[right] > target)
      right--;
    else
      left++;
  }
  //find index
  const ret = []
  for(let i=0; i<nums.length; i++){
    if(nums[i] === sorted_nums[left] || nums[i] === sorted_nums[right])
      ret.push(i)
  }
  return ret
};

总结

在 哈希部分已经做过这道题了，对于这道题哈希确实是最好的解法，但也有必要借这题练习下双指针的思想。