/* All Contributors (C) 2020 */
package io.github.dreamylost.practice;

/**
 * @description 输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S， 如果有多对数字的和等于S，输出两个数的乘积最小的。 输出描述:
 *     对应每个测试案例，输出两个数，小的先输出。
 * @author Mr.Li
 */
public class FindNumbers {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        java.util.ArrayList<Integer> list = new FindNumbers().FindNumbersWithSum(array, 15);
        for (Integer integer : list) {
            System.out.print(integer);
        }
    }

    /**
     * @description 使用夾逼 數組必須是已經排序的
     * @param array
     * @param sum
     * @return
     * @time 20点25分
     */
    public java.util.ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {

        java.util.ArrayList<Integer> list = new java.util.ArrayList<>();
        if (array == null || array.length == 0) return list;
        int len = array.length;
        int end = len - 1;
        int begin = 0;
        int muti = 0;
        while (begin < end) {
            int currSum = array[begin] + array[end];
            if (sum == currSum) {
                // 满足条件的第一对
                if (list.size() == 0) {
                    // 保存乘积
                    muti = array[begin] * array[end];
                    list.add(array[begin]);
                    list.add(array[end]);
                } else {
                    // 满足条件的第2队 判断是否大于前面一对的乘积
                    if (array[begin] * array[end] < muti) {
                        muti = array[begin] * array[end];
                        // 清空链表，重新填入
                        list.clear();
                        list.add(array[begin]);
                        list.add(array[end]);
                    }
                }
                begin++;
                end--;
            } else {
                if (currSum < sum) {
                    begin++;
                } else {
                    end--;
                }
            }
        }
        return list;
    }
}
