Sword finger offer II 006 Sort the sum of two numbers in the array

subject

Given a has been according to Ascending order Array of integers for numbers , Please find out two numbers from the array, and the sum of them is equal to the target number target .

Functions should be length based 2 Returns the subscript values of the two numbers in the form of an array of integers .numbers The subscript from 0 Start counting , So the answer array should satisfy 0 <= answer[0] < answer[1] < numbers.length .

Suppose that there is only one pair of qualified numbers in the array , At the same time, a number cannot be used twice .

Example

Input ：numbers = [1,2,4,6,10], target = 8
Output ：[1,3]
explain ：2 And 6 The sum is equal to the number of targets 8 . therefore index1 = 1, index2 = 3 .

Input ：numbers = [2,3,4], target = 6
Output ：[0,2]

Input ：numbers = [-1,0], target = -1
Output ：[0,1]

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/kLl5u1
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Method 1： Hashtable

class Solution {
    
    public int[] twoSum(int[] numbers, int target) {
    
        int n = numbers.length;
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
    
            int a = target - numbers[i];
            int b = numbers[i];

            if(map.containsKey(a)) return new int[]{
    map.get(a), i};
            map.put(b, i);
        }
        return new int[]{
    };
    }
}

Method 2： Double pointer

The title is ascending array

Java Realization

class Solution {
    
    public int[] twoSum(int[] numbers, int target) {
    
        int n = numbers.length;

        int l = 0, r = n - 1;

        while (l < r) {
    
            if (numbers[l] + numbers[r] == target) return new int[]{
    l, r};
            else if (numbers[l] + numbers[r] > target) r--;
            else l++;
        }

        return new int[]{
    };
    }
}