Skip to content

和为S的两个数字

和为S的两个数字

题目描述

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

解法

定义两个指针，start指向数组头，end指向数组末尾。如果：

  • sum == array[start] + array[end]，则返回结果
  • sum > array[start] + array[end]，则start++，因为数组是递增的，所以从小数右边找一个大数与 array[end] 求和再次判断
  • 否则 end--
/**
 * @author mcrwayfun
 * @version v1.0
 * @date Created in 2019/02/02
 * @description
 */
public class Solution {

    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {

        ArrayList<Integer> reList = new ArrayList<>();

        if (array == null || array.length < 2 || sum <= array[0]) {
            return reList;
        }

        int start = 0;
        int end = array.length - 1;

        while (start < end) {

            int curSum = array[start] + array[end];
            if (curSum == sum) {
                reList.add(array[start]);
                reList.add(array[end]);
                return reList;
            } else if (curSum < sum) {
                start++;
            } else {
                end--;
            }
        }

        // 查无
        return reList;
    }
}

测试用例

  1. 功能测试（数组中存在和为 s 的两个数；数组中不存在和为 s 的两个数）；
  2. 特殊输入测试（表示数组的指针为空指针）。
回到顶部