题目

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：

输入：nums = [2,7,11,15], target = 9

输出：[2,7] 或者 [7,2]

示例 2：

输入：nums = [10,26,30,31,47,60], target = 40

输出：[10,30] 或者 [30,10]

限制：

1 <= nums.length <= 10^5

1 <= nums[i] <= 10^6

思路

利用 HashMap 可以通过遍历数组找到数字组合，时间和空间复杂度均为 O(N)；

注意本题的 nums 是 排序数组 ，因此可使用 双指针法 将空间复杂度降低至 O(1)。

双指针分别指向nums的头部和尾部，然后逐渐像中间靠拢，直到找到和为target的两个数字

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let p1 = 0 // 左侧指针
    let p2 = nums.length - 1 // 右侧指针
    // 循环结束条件为左侧指针位置大于等于右侧指针
    while (p1 < p2) {
        const value1 = nums[p1]
        const value2 = nums[p2]
        const sum = value1 + value2
        // 和比target大的时候右侧指针向左
        if (sum > target) {
            p2--
        } 
      	// 和比target小的时候左侧指针向右
      	else if(sum < target) {
            p1++
        } 
      	// 和相等则直接返回结果
      	else if (sum === target) {
            return [value1, value2]
        }
    }
};

更多算法题

每天一道算法题——子集

每天一道算法题——宝石与石头

每天一道算法题——链表中倒数第k个节点

每天一道前端算法题--回溯算法--N皇后问题

每天一道算法题（快速排序）