【算法】有序数组的两数之和 - 二分法/双指针

题目

在一个有序数组中找到两个数，两个数之和为给定的一个数，返回两个数在数组中的下标。

原理

二分法

以第一个数为基准数，采用二分法寻找数组中与之相加等于给定数的数字，找到则返回下标，否则以第二个数为基准数，以此类推。

双指针

初始化两个指针，一个指向下标0，另一个指向最后一个数，让两个数相加，如果大于给定数，则右指针左移，否则左指针右移，直到找到和等于给定数的两个值，返回下标即可。

代码

二分法

    public static void main(String[] args) {
        int[] indexArray = getIndexArrayByBinary(10, new int[]{1, 3, 4, 5, 6, 8});
        System.out.println(Arrays.toString(indexArray));
    }

    private static int[] getIndexArrayByBinary(int num, int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int n = arr[i], low = i + 1, high = arr.length - 1;
            while (low <= high) {
                int j = (high - low) / 2 + low;
                if (n + arr[j] == num) {
                    return new int[]{i, j};
                }
                if (n + arr[j] > num) {
                    high = j - 1;
                } else if (n + arr[j] < num) {
                    low = j + 1;
                }
            }
        }
        return new int[0];
    }

双指针

    public static void main(String[] args) {
        int[] indexArray = getIndexArrayByTwoPointer(10, new int[]{1, 3, 4, 5, 6, 8});
        System.out.println(Arrays.toString(indexArray));
    }

    private static int[] getIndexArrayByTwoPointer(int num, int[] arr) {
        int left = 0, right = arr.length - 1;
        while (arr[left] + arr[right] != num) {
            if (arr[left] + arr[right] > num) {
                right--;
            } else if (arr[left] + arr[right] < num) {
                left++;
            }
        }
        return new int[]{left, right};
    }