和为N的两个数字

问题

描述

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

力扣剑指Offer 57

思路

• 遍历一次数组，遍历过程中将N和当前数差当作Key存入Map对象中，然后每次遍历时先判断N与当前元素相差是否再Map中，再则存在一组输出。
• 递增数组，则可以使用头尾指针法，分别向两边移动，将N与头指针方向的数做差，和尾指针的数做对比，大于尾指针，则头指针向右移动一位，小于尾指针则尾指针向左移动，等于则存在以租输出。

Code

题解1

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i : nums){
            int j = target-i;
            if(map.containsKey(j)){
                return new int[]{i,j};
            }
            map.put(i, j);
        }
        return null;

    }
}

题解2

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

    }
}