JZ57 和为S的两个数字

题目

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

方法1 暴力解题

思路

算法实现

两次循环，两个值相加与sum进行比较，为true直接break即可

代码

package mid.JZ57和为S的两个数字;

import java.util.ArrayList;
public class Solution {
    /**
     * 暴力计算
     * @param array
     * @param sum
     * @return
     * 运行时间     1084ms
     * 占用内存     28348KB
     */
    private ArrayList<Integer> FindNumbersWithSum1(int[] array, int sum) {
        ArrayList<Integer> res = new ArrayList<>();
        if(array.length == 0) return res;
        for(int i = 0; i < array.length; i++) {
            for(int j = 0; j < array.length; j++) {
                if(array[i] + array[j] == sum) {
                    res.add(array[i]);
                    res.add(array[j]);
                    return res;
                }
            }
        }
        return res;
    }
}

方法2 双指针

思路

算法实现

这道题目还有一个条件是数组是升序序列，在方法一中没有用到。这个条件有什么用？
既然数组是有序的，那我们肯定知道和找到一定程度就不找了，我们为什么要从最小的两个数开始相加呢？
我们可以用二分法的思路，从中间开始找。

使用双指针指向数组第一个元素和最后一个元素，然后双指针对撞移动，如果两个指针下的和正好等于目标值sum，那我们肯定找到了，如果和小于sum，说明我们需要找到更大的，那只能增加左边的元素，如果和大于sum，说明我们需要找更小的，只能减小右边的元素。

具体做法：

step 1：准备左右双指针分别指向数组首尾元素。
step 2：如果两个指针下的和正好等于目标值sum，则找到了所求的两个元素。
step 3：如果两个指针下的和大于目标值sum，右指针左移；如果两个指针下的和小于目标值sum，左指针右移。
step 4：当两指针对撞时，还没有找到，就是数组没有。

代码

package mid.JZ57和为S的两个数字;

import java.util.ArrayList;
public class Solution {
    /**
     * 双指针
     * @param array
     * @param sum
     * @return
     * 运行时间
     * 250ms
     * 占用内存
     * 27188KB
     */
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> res = new ArrayList<>();
        int left = 0, right = array.length - 1;
        while(left < right) {
            if (array[left] + array[right] == sum) {
                res.add(array[left]);
                res.add(array[right]);
                return res;
            } else if (array[left] + array[right] < sum){
                left++;
            } else {
                right--;
            }
        }
        return res;
    }
}