剑指offer（四十二） 和为S的两个数字

点击进入 牛客网题库：和为S的两个数字

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

方法一 硬来

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        int len = array.length;

        for(int i = 0; i < len; i++) {
            for(int j = i + 1; j < len; j++) {
                if(array[i] + array[j] == sum) {
                    if(list.size() == 0) {
                        list.add(array[i]);
                        list.add(array[j]);
                    } else {
                        int last = array[i]*array[j];
                        int current = list.get(0) * list.get(1);
                        if(last < current) {
                            list.add(array[i]);
                            list.add(array[j]);
                        }
                    }
                }
            }
        }
        
        return list;
    }
}

方法二 利用题目给出的 递增排序

因为 a + b = S
可以拆分成 (a-x) + (b+x) = S

(a-x) * (b+x) - ab
判断这个值是 小于零，证明两边的和相等的情况下 (a-x) * (b+x) 是问题的解
得出：x(a-b-x) x因为是大于0的，a<b, 所以这个值，是小于0， 所以(a-x) * (b+x) 是问题的解

通过上述来说，就可以进行2分求解值

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        int start = 0;
        int last = array.length - 1;
        while(start < last) {
            if(array[start]+ array[last] > sum) {
                last-- ;
            } else if(array[start] + array[last] < sum) {
                start++;
            } else if(array[start] + array[last] == sum) {
                list.add(array[start]);
                list.add(array[last]);
                break;
            }
        }
        
        return list;
    }
}