【剑指offer】57. 和为s的两个数字

57. 和为s的两个数字

题目描述

输入一个递增排序的数组和一个数字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]

解题思路

看似简单，因为是升序数组，所以一开始用暴力求解，代码如下：

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

结果超时了，转用HashMap求解。
首先当目标数组为空或只有一个值的时候，返回空。然后创建HashMap，遍历数组，将值放入HashMap，如果其中两个值相加可以得到目标值，则返回这两个值的结果。
遍历完依旧没有找到目标值，则返回空。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 当数组为空或只有一个元素的时候，返回空
        if(nums.length < 2) return new int[0];

        // 创建HashMap
        HashMap<Integer, Integer> map = new HashMap<>();
        // 遍历数组，如果找到一个值可以与target - nums[i]对应，则返回结果
        // 如果找不到对应，则把此值放入HashMap
        // 遍历完成后如果没有返回结果则返回空
        for(int i = 0; i < nums.length; i++){
            int cur = target - nums[i];
            if(map.containsKey(cur)){
                return new int[] {cur, nums[i]};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }
}