剑指offer 42.和为S的两个数字

题目

题目描述

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

输出描述:

对应每个测试案例，输出两个数，小的先输出。

思路

同样是滑动窗口题目，设置左右两个游标，然后计算和，若和小，那么左侧游标增加，区间和大，右侧游标减小，保存结果的时候要比较一下更符合条件的数。

代码

public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
  ArrayList<Integer> list = new ArrayList<>();
  int l = 0;
  int r = array.length - 1;
  int a = 0;
  int b = 0;
  int mul = Integer.MAX_VALUE;
  while (l < r) {
    int num = array[l] + array[r];
    if (num == sum) {
      int temp = array[l] * array[r];
      if (temp < mul) {
        mul = temp;
        a = array[l];
        b = array[r];
      }
      r--;
    } else if (sum > num) {
      l++;
    } else {
      r--;
    }
  }
  if (a != 0 && b != 0) {
    list.add(a);
    list.add(b);
  }
  return list;
}