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

本文阅读 1 分钟
首页 知识库 正文

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

返回的数组不唯一

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

一,常规两数之和

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

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

  1. const twoSum = (number, target) => {
  2. let left = 0,
  3. right = number.length - 1;
  4. while (left < right) {
  5. const sum = number[left] + number[right];
  6. if (sum === target) return [number[left], number[right]];
  7. // 等于目标值,返回对应值
  8. else if (sum < target) left++;
  9. // 小于目标值,左指针向右移动
  10. else right--; // 大于目标值,右指针向左移动
  11. }
  12. return null;
  13. };

一、获取其中某一种组合

  1. function twoSum(arr, target) {
  2. let first;
  3. let second;
  4. arr.forEach((element) => {
  5. if (arr.includes(target - element)) {
  6. first = element;
  7. }
  8. });
  9. second = arr.find((ele) => ele === target - first);
  10. if (!first || !second) return null;
  11. return [first, second];
  12. }

二、获取所有组合

  1. function twoSum(arr, target) {
  2. let firstArr = [];
  3. let secondArr = [];
  4. let result = [];
  5. arr.forEach((ele) => {
  6. if (arr.includes(target - ele)) {
  7. firstArr.push(ele);
  8. }
  9. });
  10. firstArr.forEach((ele) => {
  11. secondArr.push(target - ele);
  12. });
  13. firstArr.forEach((firstEle, i) => {
  14. secondArr.forEach((secondEle, j) => {
  15. if (i === j) {
  16. result.push([firstEle, secondEle]);
  17. }
  18. });
  19. });
  20. return result.length > 0 ? result : null;
  21. }

双指针法获取所有组合

  1. const twoSum = (arr, sum) => {
  2. if (arr.length <= 1) return [];
  3. let len = arr.length;
  4. let left = 0;
  5. let right = len - 1;
  6. let result = [];
  7. while (left < right) {
  8. let _sum = arr[left] + arr[right];
  9. if (_sum === sum) {
  10. result.push([arr[left], arr[right]]);
  11. left++;
  12. right--;
  13. } else if (_sum > sum) {
  14. right--;
  15. } else {
  16. left++;
  17. }
  18. }
  19. return result;
  20. };
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

求给定数组中 N 个数相加之和为 sum 所有可能集合
« 上一篇 05-28
100 层楼,两个玻璃球,求最少多少次测出能摔碎玻璃球的楼层
下一篇 » 05-28

发表评论