两数之和II_二分法||二分查找

1 题目描述

https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

2 思路

看到这一个题目，数组和有序，第一个想法就是二分查找（当然看了官方题解之后，发现还有双指针做法）。

做法很简单，给定了target，我们对数组numbers进行遍历，对于numbers的每一个元素，重新在数组中寻找和该元素之和为target的元素。如果找到的元素和遍历到的元素重复了，那么继续遍历，然后再寻找；如果不重复，那就将两个元素的位置都加一获得真实位置，然后返回。

public int[] twoSum(int[] numbers, int target) {
    int pre = 0;
    for (int i = 0; i < numbers.length; i++) {
        if (i > 0 && numbers[i] == pre) // 如果遇到重复元素，就别浪费这个时间了。
            continue;
        int other_tar = target - numbers[i];
        int pos = biSearch(numbers, other_tar);
        if (pos >= 0) {
            if (pos == i) continue; // 防止找到自己头上, 比如参数是([0,4,5], 8), 就有会找到两个4。
            return new int[]{i + 1, pos + 1}; // 索引+1变成真实位置。
        }
        pre = numbers[i]; // 记录前一个值
    }
    return null;
}

那么最重要的问题是，如何进行二分查找？

我们就事论事，如何分析这个题目呢？

相似题目可以看我的这篇文章【刷题笔记】H指数||数组||二分查找的变体

题目本身已经强调了，非递减顺序，也就是说，数组中可能会存在一些相等的元素。举个例子

towSum([1,3,4,4], 8)

当我们遍历到第一个4的时候，为了让和为8，我们需要在数组中找到另一个为4的元素。如果二分是普通的二分查找：

 if (numbers[mid_index] == num) {return mid_index;}
else if (numbers[mid_index] < num) l = real_mid + 1;
else r = real_mid - 1;

我们极有可能在碰到第一个4的时候，就返回了其坐标，而这和我们题目中的要求是冲突的。那么我们就会接着遍历numbers数组，碰到第二个4，然后继续进行二分查找，找到了第一个4，返回位置，发现这个组合是符合要求的，最后我们返回的两个位置是[4,3]。我替你们试过了，就算你返回的的两个坐标是对的，还是要保证坐标是从小到大的，反过来也会报错。

怎么解决这种存在多个相等元素的问题呢？我的解决方法是分成两步：

1. 遍历numbers的时候，遇到重复元素，只遍历第一个。上面代码中的：

 if (i > 0 && numbers[i] == pre) // 如果遇到重复元素，就别浪费这个时间了。
        continue;

就是解决这个问题的。

2. 在二分查找的时候，只找重复元素的最后一个。这样假设碰到多个重复元素，而且恰好两个重复元素之和等于我们target的情况，最终返回的坐标一定是递增顺序的。

那么我们接下来考虑，怎么在二分查找的时候，找到最后一个符合条件的元素呢？

对于二分查找有两个最重要的问题：如何计算mid，如何跳转left和right。

我在【刷题笔记】H指数||数组||二分查找的变体这篇博客中提出了一个思考的范式：

这个两个问题本身是一个问题，只要我们确定了如何跳转left和right，就能确定如何计算mid。

（这只是我的一点浅薄的看法，大家要根据自己的刷题情况实时更新自己的理念，我考虑出来的东西也不一定具有普适性，我只是刚刷题的菜鸡。）

怎么理解上面这句话呢？比如我们这道题，我们确定了目标是寻找满足条件（即等于other_tar）的最后一个元素，也就是右边界，一个很符合直觉的想法就是，left指针是不断右移的，要找右边界，left指针最合适。

那么我们看到，当遇到这种情况的时候，numbers[mid]==other_tar，mid可能是右边界吗？可能。那mid右边的位置还可能是右边界吗？不一定。如果left移动到mid右边，会不会错过右边界？可能会。所以，为了避免这种跳过边界的可能性，当mid满足条件的时候，我们不是直接返回mid，而是让left转移到mid的位置上，通过left不断寻找右边界。而当numbers[mid] < other_tar的时候，让left++；当numbers[mid] > other_tar的时候，right--，这些都是常规操作了。

也就是说，当查找边界的时候，我们的left指针最后可能会指向边界。为什么是可能？因为数组里可能没有我们要找的值，这时候left一路向右，势不可挡，直接窜到了数组的边界之外，也是可能的。

现在我们解决了第二个问题，如何跳转left和right。那么我们回过头解决第一个问题，如何计算mid。

第二个问题，我们可以直接考虑在只剩下两个元素的时候（即只剩下left和right的时候），该如何计算mid。

众所周知，当我们在只剩下两个元素的时候，mid元素要么是(left + right) / 2，放在left上，要么是(left + right) / 2 + 1，放在right上。

我们已经确定了，left在某些条件下是可能直接跳转到mid上的， 如果让mid=left，下一步如果left需要跳转，left=mid，然后mid=left。。。。。。无限循环。

所以，为了避免死循环，当只有偶数个元素的时候，我们需要让mid跳转到中间两个元素的后一个元素上。所以我说，当我们确定了left和right的跳转问题之后，如何计算mid的问题就迎刃而解。

当然，传统的二分法，left跳转到mid+1，right跳转到mid-1，不会出现死循环的。咱们现在讨论的是边界问题，所以有些特殊。

我还是那句话，我花生豆大的小脑仁接受不了太多弯弯绕绕，面对二分问题的时候，left和right的取值，我倾向于直接使用真实位置，即从1开始的位置。

public int biSearch(int[] numbers, int num) {
    int l = 1, r = numbers.length;
    ...
}

这样有一个好处就是符合我们的思维直觉，本身二分法的变化就多，能简化思考的地方就简化思考。

那么如果l~r范围内（闭区间）的元素个数是奇数个，(l+r)/2就是中间数的真实位置，如果是偶数个，我们就设为(l+r)/2 + 1。这个方法虽然笨，但是符合我们的思维直觉。

 public int biSearch(int[] numbers, int num) {
    int l = 1, r = numbers.length;
    while (l < r) { // 一旦两个指针重合，遍历结束，要么是找到了，要么是l跳到边界外了。
        int real_mid = (l + r) / 2 + ((l - r + 1) % 2 == 0 ? 1 : 0);
        int mid_index = real_mid - 1;
        if (numbers[mid_index] == num) l = real_mid;
        else if (numbers[mid_index] < num) l = real_mid + 1;
        else r = real_mid - 1;
    }
    if (l <= numbers.length && numbers[l-1] == num) return l-1;
    else return -1;
}

在这里，所有的指针我都使用了真实值，只有在用到numbers[mid_index]的时候，才用的索引。当然，这些都是我自己的习惯。

因为我们是用left指针来判断边界，left在跳转的过程中，我们计算mid的时候是选择了靠右型，如果left跳转到mid+1的位置，可能跳出边界。

所以我们最后的判断条件是if (l <= numbers.length && numbers[l-1] == num) return l-1;
返回索引。

3 代码

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int pre = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (i > 0 && numbers[i] == pre)
                continue;
            int other_tar = target - numbers[i];
            int pos = biSearch(numbers, other_tar);
            if (pos >= 0) {
                if (pos == i) continue;
                return new int[]{i + 1, pos + 1};
            }
            pre = numbers[i];
        }
        return null;
    }

    public int biSearch(int[] numbers, int num) {
        int l = 1, r = numbers.length;
        while (l < r) {
            int real_mid = (l + r) / 2 + ((l - r + 1) % 2 == 0 ? 1 : 0);
            int mid_index = real_mid - 1;
            if (numbers[mid_index] == num) l = real_mid;
            else if (numbers[mid_index] < num) l = real_mid + 1;
            else r = real_mid - 1;
        }
        if (l <= numbers.length && numbers[l-1] == num) return l-1;
        else return -1;
    }
}