本文主要是介绍TypeScript算法每日一题:两数之和(167),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
作者:前端小王hs
阿里云社区博客专家/清华大学出版社签约作者✍/CSDN百万访问博主/B站千粉前端up主
题库:力扣
题目序号:167(中等)
题目:
给你一个下标从1开始的整数数组 numbers ,该数组已按非递减顺序排列,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入只对应唯一的答案 ,而且你不可以重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1:
输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
解题思路:
这里需要注意的几个条件是
①下标从1开始👉得到的结果要加1
②非递减顺序排列👉递增
③不可以重复使用相同元素👉下标不能一样
④必须只使用常量级的额外空间👉传入的是大小为n的数组,如果我们使用了大小为n或与n成正比的数组去存储计算的中间结果,那么就没有使用常量级
由于这是一个递增的数组,那么基础的解题思路是可以采用暴力枚举的思路(点击跳转暴力枚举解法)
另外,还可以采用双向指针的思路,也就是从数组的第一项
和最后一项
去双向奔赴,那么需要注意的是,由于数组是非递减顺序排列的,所以如果得到的结果小于tagget
,那么应该是左边的下标+1
,反之则是右边下标-1
,这也很好理解,例如示例1的数组[2,7,11,15]
,第一次是2+15=17
,大于目标数9
,那么右边的数就应该从15
退到11
,也就是right--
解题代码:
function twoSum(numbers: number[], target: number): [number, number] | null { let left = 0;// 注意,由于数组从0开始,所以最后一项是length-1let right = numbers.length - 1; while (left < right) { const sum = numbers[left] + numbers[right]; // 判断结果,如果相等直接returnif (sum === target) { return [left + 1, right + 1];// 当和小于目标数时 } else if (sum < target) { left++;// 当和大于目标数时} else { right--; } } return null;
}
解题过程示例:
示例1的数组[2,7,11,15]
,第一次是2+15=17
,大于目标数9
,那么右边的数就应该从15
退到11
,也就是right--
,直至2+7=9
,此时得到下标数组[0,1]
,然后下标都加1
满足题意
这篇关于TypeScript算法每日一题:两数之和(167)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!