【Q681】求正序增长的正整数数组中，其和为 N 的两个数

[shfshanyue]

//=> [5, 10]
twoSum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 15)

//=> null
twoSum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 150)

[shfshanyue]

TODO

[hengistchan]

const twoSum = (arr, sum) => {
  if (arr.length < 2 || arr[arr.length - 1] + arr[arr.length - 2] < sum) {
    return null
  }
  const sumList = {}, res = []
  for (let i = 0; i < arr.length; i++) {
    let val = arr[i]
    if (sumList[val]) {
      res.push([Math.min(val, sumList[val]), Math.max(val, sumList[val])])
    } else {
      sumList[sum - val] = val
    }
  }
  return res.length === 0 ? null : res
}
twoSum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 15)  // [[7, 8], [6, 9], [5, 10]]

返回的数组不唯一

[AaronKwong929]

一，常规两数之和

var twoSum = function (nums, target) {
    const hash = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (hash.has(target - nums[i])) return [nums[i], nums[target - i]];
        hash.set(nums[i], i);
    }
    return null;
};

二，双指针 利用题目的提示 “正序增长的正整数数组” 而且例1的提示很明显了，左右两个指针 当前和大于目标值，右指针左移 当前和小于目标值，左指针右移 左指针等于右指针，循环中断，返回null

const twoSum = (number, target) => {
    let left = 0,
        right = number.length - 1;
    while (left < right) {
        const sum = number[left] + number[right];
        if (sum === target) return [number[left], number[right]]; // 等于目标值，返回对应值
        else if (sum < target) left++; // 小于目标值，左指针向右移动
        else right--; // 大于目标值，右指针向左移动
    }
    return null;
};

[JoeWrights]

一、获取其中某一种组合

function twoSum(arr, target) {
  let first
  let second
  arr.forEach(element => {
    if (arr.includes(target - element)) {
      first = element
    }
  })
  second = arr.find(ele => ele === target - first)

  if (!first || !second) return null

  return [first, second]
}

二、获取所有组合

function twoSum(arr, target) {
  let firstArr = []
  let secondArr = []
  let result = []

  arr.forEach(ele => {
    if (arr.includes(target - ele)) {
      firstArr.push(ele)
    }
  })

  firstArr.forEach(ele => {
    secondArr.push(target - ele)
  })

  firstArr.forEach((firstEle, i) => {
    secondArr.forEach((secondEle, j) => {
      if (i === j) {
        result.push([firstEle, secondEle])
      }
    })
  })

  return result.length > 0 ? result : null
}

[hwb2017]

双指针法获取所有组合

const twoSum = (arr, sum) => {
    if (arr.length <= 1) return []
    let len = arr.length
    let left = 0
    let right = len - 1
    let result = []
    while (left < right) {
      let _sum = arr[left] + arr[right]
      if (_sum === sum) {
        result.push([arr[left], arr[right]])
        left++
        right--
      } else if (_sum > sum) {
        right--  
      } else {
        left++ 
      }
    }
    return result
}

[Ghaining]

function twoSum(arr, target) {
  const map = {};
  for (let i = 0; i < arr.length; i++) {
    const num = arr[i];
    const diff = target - num;
    if (map[diff] !== undefined) {
      return [map[diff], arr[i]];
    }
    map[num] = arr[i];
  }
  return null;
}

[Ghaining]

var twoSum = function (nums, target) { const hash = new Map(); for (let i = 0; i < nums.length; i++) { const diff = target - nums[i]; if (hash.has(diff)) return [i, hash.get(diff)]; hash.set(nums[i], i); } return null; };

第一个有点问题，应该是这样

[Ghaining]

一，常规两数之和

var twoSum = function (nums, target) {
    const hash = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (hash.has(target - nums[i])) return [nums[i], nums[target - i]];
        hash.set(nums[i], i);
    }
    return null;
};

二，双指针 利用题目的提示 “正序增长的正整数数组” 而且例1的提示很明显了，左右两个指针 当前和大于目标值，右指针左移 当前和小于目标值，左指针右移 左指针等于右指针，循环中断，返回null

const twoSum = (number, target) => {
    let left = 0,
        right = number.length - 1;
    while (left < right) {
        const sum = number[left] + number[right];
        if (sum === target) return [number[left], number[right]]; // 等于目标值，返回对应值
        else if (sum < target) left++; // 小于目标值，左指针向右移动
        else right--; // 大于目标值，右指针向左移动
    }
    return null;
};

var twoSum = function (nums, target) {
  const hash = new Map();
  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];
    if (hash.has(diff)) return [i, hash.get(diff)];
    hash.set(nums[i], i);
  }
  return null;
};

第一个有点小问题