167. Enter the sum of two numbers into an ordered array (2021/12/16)

Topic link

167. Sum of two numbers II – Enter ordered array

The title

Given an array of integers in non-decreasing order, numbers,

Find two numbers in the array that add up to the target number.

The function should return the subscript values of these two numbers as an array of integers of length 2. The subscript of numbers starts at 1, so the answer array should be 1 <= answer[0] < answer[1] <= numbers. Length.

You can assume that each input corresponds to a unique answer, and you can’t reuse the same elements.

The sample

• The sample a

Numbers = [2,7,11,15] target = 9 output: [1,2] So index1 = 1, index2 = 2.Copy the code

• Example 2

Numbers = [2,3,4] target = 6Copy the code

• Example 3

Numbers = [-1,0] target = -1Copy the code

• prompt

  2 <= numbers. Length <= 3 * 104-1000 <= numbers[I] <= 1000 numbers in non-decreasing order -1000 <= target <= 1000 Only one valid answer existsCopy the code

Methods to solve

Brute force

• code

public int[] twoSum(int[] numbers, int target) {

    int n = numbers.length;
    // Double loop judgment
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int sum = numbers[i] + numbers[j];
            if (sum == target) {
                if (i == j && numbers[i] == numbers[j]) {
                    continue;
                }
                return new int[]{i + 1, j + 1}; }}}return new int[] {-1, -1};
}
Copy the code

Double pointer

• code

public int[] twoSum(int[] numbers, int target) {
    int n = numbers.length;
    int l = 0;
    int r = n - 1;
    while (l <= r) {
        int sum = numbers[l] + numbers[r];
        if (sum == target) {
            return new int[]{l + 1, r + 1};
        } else if (sum > target) {
            r--;
        } else{ l++; }}return new int[] {-1, -1};
}
Copy the code

Binary search

• code

public int[] twoSum(int[] numbers, int target) {
    int n = numbers.length;
    for (int i = 0; i < n; i++) {
        int l = i + 1;
        int r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (numbers[mid] + numbers[i] == target) {
                return new int[]{i + 1, mid + 1};
            } else if (numbers[mid] + numbers[i] > target) {
                r = mid - 1;
            } else {
                l = mid + 1; }}}return new int[] {-1, -1};
}
Copy the code

Hash table

• code

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 value = target - numbers[i];
        if (map.containsKey(value)) {
            return new int[]{map.get(value) + 1, i + 1};
        } else{ map.put(numbers[i], i); }}return new int[] {-1, -1};
}
Copy the code

The results summary

According to the time and space results of the four methods, brute force cracking takes the longest time and is also the slowest solution. Although the space of the four methods is almost the same, in terms of time, the dual-pointer efficiency is the highest and brute force cracking efficiency is the lowest.