题解 | #和为S的两个数字#

import java.util.*;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> result = new ArrayList<>();
        if (array == null || array.length == 0 || sum == 0) {
            return result;
        }
        int left = 0;
        int right = array.length - 1;
        while (left != right && left < array.length && right > 0) {
            if (array[right] >= sum) {
                right--; //先找到最接近sum的数值
            }
            //再进去左右微调操作，直到相等||左右浮标相撞为止。
            else if (array[left] + array[right] == sum) {
                result.add(array[left]);
                result.add(array[right]);
                break;
            } else if (array[left] + array[right] > sum) { //如果加起来仍然偏大，代表右边的数依然偏大，右浮标向左调
                right--;
            } else { //如果加起来仍然偏小，代表左边的数不够大，则左边向右调
                left++;
            }
        }
        return result;
    }
}

通过对数列找到最接近但小于sum的数，定义为right。再定义数列最小的数为left。在迭代时如果left和right对应下标的值的和比sum大，代表right还是偏大，向左调整寻找更小的数；如果迭代到left和right下标对应值的和比sum小，left向右找更大的数进行匹配；反复迭代到找到left和right对应的值的和为sum的值，然后输出。后者left和right下标相撞后，输出空数组。