剑指offer - 和为S的两个数字(Java实现)

题目链接：https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b?tpId=13&&tqId=11195&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：首先第一反应就是二分，一个有序数组，和为S的两个数，比较经典的二分题目，直接遍历数组，每一个项的值为 val，使用二分的方法直接判断 S - val 是否在这个数组中即可。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        int Min = Integer.MAX_VALUE, n = array.length;
        ArrayList<Integer> list = new ArrayList<>();
        int x1 = 0, y1 = 0;
        for(int val : array) {
            if(binary_serach(array, sum - val)) {
                if(Min > val * (sum - val)) {
                    Min = val * (sum - val);
                    x1 = val;
                    y1 = sum - val;
                }
            }
        }
        if(x1 != 0) list.add(x1); //需要注意最后没有找到的情况
        if(y1 != 0) list.add(y1);
        return list;
    }
    public boolean binary_serach(int[] array, int val) {
        int l = 0, r = array.length - 1;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(array[mid] < val) {
                l = mid + 1;
            } else if(array[mid] > val) {
                r = mid - 1;
            } else return true;
        }
        return false;
    }
}

  思路二：双指针，我们设置两个指针，一个指向最左边 l，一个指向最右边 r，那么有下面三种情况。

• array[l] + array[r] = sum, 此结果即为一组合法的答案，如果我们想要找到其他的答案我们需要：--i, ++ j, 继续寻找其他答案。
• array[l] + array[r] < sum, 说明结果偏小，那么答案需要偏大，我们需要 ++ i。
• array[l] + array[r] > sum, 说明结果偏大，那么答案需要偏小，我们需要 -- j。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        int Min = Integer.MAX_VALUE, n = array.length;
        ArrayList<Integer> list = new ArrayList<>();
        int x1 = 0, y1 = 0;
        int i = 0, j = n - 1;
        while(i < j) {
            if(array[i] + array[j] == sum) {
                if(Min > array[i] * array[j]) {
                    Min = array[i] * array[j];
                    x1 = array[i];
                    y1 = array[j];
                }
                ++ i; -- j;
            } else if(array[i] + array[j] < sum) ++ i;
              else if(array[i] + array[j] > sum) -- j;
        }
        if(x1 != 0) list.add(x1);
        if(y1 != 0) list.add(y1);
        return list;
    }
}