Leetcode advanced road - 167 Sum of two numbers II - input ordered array

 Given that one is in ascending order   Ordered array of , Find two numbers so that the sum of them is equal to the target number .

 The function should return these two subscript values  index1  and  index2, among  index1  Must be less than  index2.

 explain :

 Subscript value returned （index1  and  index2） Not from scratch .
 You can assume that each input only corresponds to a unique answer , And you can't reuse the same elements .

 Example :

 Input : numbers = [2, 7, 11, 15], target = 9
 Output : [1,2]
 explain : 2  And  7  The sum is equal to the number of targets  9 . therefore  index1 = 1, index2 = 2 .

Copy

Both solutions to this problem are common , Learn to draw inferences from one example .

• 1、 Double finger needling Define the first and last two pointers , Add the values of two , If the number obtained is greater than the target number , Then the tail pointer minus one ; If the number obtained is less than the target number , Then the header pointer plus 1. If the obtained number is equal to the target number, it directly returns two subscripts plus 1.
• 2、 Dichotomy search Binary search is to set a number first , And then binary search the following numbers , Check whether it meets the requirements .

Official explanation ： Find two numbers in the array , Make their sum equal to the target value , You can fix the first number first , Then look for the second number , The second number is equal to the difference between the target value minus the first number . Using the ordered nature of arrays , You can find the second number by binary search . In order to avoid repeated search , When looking for the second number , Look only to the right of the first number .

/**
 * 167.  Sum of two numbers  II -  Input an ordered array 
 * @Author: lixj
 * @Date: 2020/10/9 14:25
 */
public class TwoSumIIInputarrayissorted {
    /**
     *  Double finger needling 
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length-1;
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum > target) {
                j--;
            } else if (sum < target) {
                i++;
            } else {
                return new int[]{i+1, j+1};
            }
        }

        return new int[]{-1, -1};
    }

    /**
     *  Dichotomy search 
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum1(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; ++i) {
            int low = i + 1;
            int high = numbers.length -1;
            while (low <= high) {
                int mid = (high - low) /2 + low;
                if (numbers[i] + numbers[mid] < target) {
                    low = mid + 1;
                } else if (numbers[i] + numbers[mid] > target) {
                    high = mid - 1;
                } else {
                    return new int[]{i+1, mid+1};
                }
            }
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2, 7, 11, 13, 14};
        TwoSumIIInputarrayissorted test = new TwoSumIIInputarrayissorted();
        int[] a = test.twoSum1(nums, 10);
        for (int i = 0; i < 2; i++) {
            System.out.print(a[i] + " ");
        }
    }
}

Copy

Copyright: use Creative Commons signature 4.0 International license agreement to license Links:https://lixj.fun/archives/167 Sum of two numbers ii- Input an ordered array