• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Topic describes

Given an array of integers in non-decreasing order numbers, find two numbers 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.

Example 1:

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

Answer key

1. The binary

Public int twoSum(int[] twoSum(int[] twoSum, int target) {twoSum(int[] twoSum, int target) {twoSum(int[] twoSum, int target) {twoSum(int[] twoSum, int target) {twoSum(int[] twoSum, int target) {twoSum(int[] twoSum, int target) {twoSum(int[] twoSum, int target); int right = 0; int leftValue = 0; int rightValue = 0; Int flag = 0; While (left < numbers. Length -1) {leftValue = numbers[left]; right = numbers.length -1; While (right > left) {rightValue = numbers[right]; if (leftValue + rightValue == target) { flag = 1; break; } right --; } if (flag ==1) { break; } left ++; } int[] result = {left+1,right+1}; return result; }Copy the code

2. Use double Pointers to compare indentation

Two more temporary Pointers are used to replace the minor loop, which is replaced by two Pointers to Temp when the major loop executes a full circle

1. Two temporary Pointers start at left and right positions. The temporary pointer is added to compare with the target value. Because it is sorted in order, if it is larger than the target value, the right temporary pointer moves one step to the left; if it is larger than the target value, the left temporary pointer moves one step to the right. 2. When two temporary Pointers encounter each other, the loop is not found. So the left and right Pointers are further inwards, and the two temporary Pointers are equal to the left and right Pointers

  • When less than, the left pointer goes further back.
  • When greater than, the right pointer steps forward.
  • When the two meet, they close the loop. The Pointers all step forward.

Note: Temporary pointer assignments need to be evaluated when small loops meet. Leaving it outside will have an effect on each cycle.

public static int[] twoSum(int[] numbers, int target) {
        // With each move, the right pointer moves from the end of the array to the left
        int left = 0;
        int right = numbers.length -1;
        int leftValue = 0;
        int rightValue = 0;
        int leftTemp = 0;
        int rightTemp = right;
        while (left < right) {
            leftValue = numbers[leftTemp];
            rightValue = numbers[rightTemp];
            if (leftValue + rightValue < target) {
                leftTemp ++;
            }else if (leftValue + rightValue > target) {
                rightTemp --;
            }else
                break;
            // Skip this time
            if(leftTemp == rightTemp) { left ++; right --; leftTemp = left; rightTemp = right; }}int[] result = {leftTemp+1,rightTemp+1};
        return result;
    }
Copy the code