极客时间返利平台,你可以在上边通过山月的链接购买课程,并添加我的微信 (shanyue94) 领取返现。
每天晚上九点 B站讲解前端工程化直播,并解答相关问题。

# 求正序增长的正整数数组中,其和为 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 new window)

TODO

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

返回的数组不唯一

一,常规两数之和

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

一、获取其中某一种组合

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 new window)

双指针法获取所有组合

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;
};
Last Updated: 11/27/2021, 10:11:48 AM