高级前端
手写代码
【Q681】求正序增长的正整数数组中,其和为 N 的两个数

求正序增长的正整数数组中,其和为 N 的两个数

更多描述

//=> [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);

Issue 欢迎在 Gtihub Issue 中回答此问题: Issue 700 (opens in a new tab)

Author 回答者: shfshanyue (opens in a new tab)

TODO

Author 回答者: hengistchan (opens in a new tab)

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]]

返回的数组不唯一

Author 回答者: AaronKwong929 (opens in a new tab)

一,常规两数之和

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;
};

Author 回答者: JoeWrights (opens in a new tab)

一、获取其中某一种组合

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;
}

Author 回答者: hwb2017 (opens in a new tab)

双指针法获取所有组合

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;
};

Author 回答者: Ghaining (opens in a new tab)

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;
}

Author 回答者: Ghaining (opens in a new tab)

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; };

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

Author 回答者: Ghaining (opens in a new tab)

一,常规两数之和

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;
};

第一个有点小问题