求正序增长的正整数数组中,其和为 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);
返回的数组不唯一
- 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;
- }
双指针法获取所有组合
- 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;
- };
解压密码: detechn或detechn.com
免责声明
本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。