剑指offer(四十二)-和为S的两个数字(Java版)

描述

输入一个递增排序的数组array和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。

数据范围:

0<=len(array)<=105

1<=array[i]<=106

示例1

输入：[1,2,4,7,11,15],15

返回值：[4,11]

说明：返回[4,11]或者[11,4]都是可以的

示例2

输入：[1,5,11],10

返回值：[]

说明：不存在，返回空数组

示例3

输入：[1,2,3,4],5

返回值：[1,4]

说明：返回[1,4],[4,1],[2,3],[3,2]都是可以的

双重循环即可，采用最笨的方式，外层从第一个开始循环，内层循环从第二个开始，取到符合要求的值返回即可。代码如下

public ArrayList firstFindNumbersWithSum(int [] array, int sum) {
        ArrayList list = new ArrayList<>();
        if(null == array || array.length < 1 || sum < 1){
            return list;
        }
        boolean flag = false;
        for (int i = 0; i < array.length; i++) {
            for (int j = i+1; j < array.length; j++) {
                if(array[i] + array[j] == sum){
                    list.add(array[i]);
                    list.add(array[j]);
                    flag = true;
                    break;
                }
                if(array[i] + array[j] > sum){
                    break;
                }
            }
            if(flag){
                break;
            }
        }
        return list;
    }

当然 第一种解法可以优化一些，在内层循环的时候，可以采用二分法来减少循环次数。

分别从左右两头开始循环，即从第一个往后开始循环，最后一个树往前开始循环，这样就只用循环一次便可以解决问题，代码如下

public ArrayList secondFindNumbersWithSum(int [] array, int sum) {
        ArrayList list = new ArrayList<>();
        if(null == array || array.length < 1 || sum < 1){
            return list;
        }
        int begin = 0;
        int end = array.length - 1;
        while (begin < end){
            int result = array[begin] + array[end];
            if(result == sum){
                list.add(array[begin]);
                list.add(array[end]);
                break;
            }else if(result < sum){
                begin++;
            }else {
                end--;
            }
        }
        return list;
    }