题目描述

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

题解一

第一种是暴力法，双重循环寻找和为target的两个数。

时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(1)$ 。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i]+nums[j] == target) {
                    return new int[] {nums[i], nums[j]};
                }
            }
        }
        return new int[] {};
    }
}

题解二

遍历一遍数组，建立一个集合用于存储已遍历的数字。如果target减去当前数字的值不在集合中，就将当前数字存入集合中；如果对应值在集合中，就返回结果。

时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.contains(target-num)) {
                set.add(num);
            } else return new int[] {target-num, num};
        }
        return new int[] {};
    }
}

题解三

由于数组已经排序，所以可以用类似夹逼的思想，用双指针实现。

如果left+right的值小于sum，说明要找的数字在right左边，right--；
如果left+right的值大于sum，说明要找的数字在left右边，left++；
如果left+right的值等于sum，则找到结果。

时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$ 。

下面是参考代码：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while (left < right) {
            if (nums[left] + nums[right] < target)
                left++;
            else if (nums[left] + nums[right] > target)
                right--;
            else {
                return new int[] {nums[left], nums[right]};
            }
        }
        return new int[] {};
    }
}