和为s的两个数字

题目：

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

示例

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

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

思考：

提示

• 直观想法可以使用一个 HashMap，key 为 target - nums[i]，value 为 nums[i]，每次判断 map.containsKey(nums[i])，存在就返回，不存在就 put

• 但是这样时间和空间复杂度均为 O(N)

• 注意题意为排序数组，很容易想到使用双指针，从数组两边向中间寻找，相遇跳出

题解：

双指针

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

HashMap

class Solution {
    public int[] twoSum(int[] nums, int target) {

        Map<Integer,Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])){
                return new int[]{nums[i],map.get(nums[i])};
            }else {
                map.put(target - nums[i],nums[i]);
            }
        }
        return new int[0];
    }
}