57 和为s的两个数字

剑指 Offer 57. 和为s的两个数字

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

解题思路：

因为给定的数组是有序的，这里可以用双指针来解题。

通过 $start$ 和 $end$ 指针，初始时 $start$ 指向第一个元素，$end$ 指向最后一个元素，两个元素不断向中间靠近。

靠近的过程中，判断两个指针指向的元素的和 $sum$ 是否为目标值 $target$：

• 如果 $sum = target$，说明这两个数时符合要求的，返回 $start$ 和 $end$ 指向的元素；
• 如果 $sum > target$，说明 $end$ 指向的数字太大，需要减小，$end$ 自减；
• 如果 $sum < target$，说明 $start$ 指向的数字太小，需要增大，$start$ 自增。

代码：

public int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length < 2) {
        return new int[0];
    }
    int start = 0;
    int end = nums.length - 1;
    while (start < end) {
        if (nums[start] + nums[end] == target) {
            return new int[]{nums[start], nums[end]};
        } else if (nums[start] + nums[end] > target) {
            end--;
        } else {
            start++;
        }
    }
    return new int[0];
}

复杂度分析

• 时间复杂度$O(N)$：最差情况下，需要遍历所有的元素。
• 空间复杂度$O(1)$：辅助变量占用常数大小的额外空间。