输入一个递增排序的数组和一个数字 s,在数组中查找两个数,使得它们的和正好是 s。如果有多对数字的和等于 s,输出任意一对即可。
如果这个数组不是递增的,就得用哈希表来解决,空间复杂度是 O(N)。
但是题目条件是“递增数组”,因此可以使用“双指针”的思路来实现:即一个指针指向开头,另一个指向结尾。
比较指针对应的 2 个元素的和与给定数组 s:
/**** @param {Array} data* @param {Number} sum*/function findNumsWithSum(data, sum) {if (!Array.isArray(data) || data.length <= 1) {return [null, null];}let i = 0,j = data.length - 1;while (i < j) {let now = data[i] + data[j];if (now === sum) {return [data[i], data[j]];} else if (now > sum) {--j;} else {++i;}}return [null, null];}/*** 以下是测试代码*/// 输出:[ 4, 11 ]console.log(findNumsWithSum([1, 2, 4, 7, 11, 15], 15));