Sword to Offer-57.1 和为 S 的两个数字 ❀

13 May 2020 in Algorithm

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

解题思路：

1、数组为有序的，因此取指针指向头尾，分别向中间靠拢，left+right=sum就是积最小的和为sum的两个数；

2、若和大于sum，将right左移减小和，若小于sum将left右移增大和，找到了符合条件的两个数或者right指针在left左边时循环结束。

问题图解：

AC代码：

// Find Two Number Sum S And Multiply Smallest in Sorted Array

import java.util.ArrayList;



public class Solution {
    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]);
                break;
            }
            else if (array[left] + array[right] < sum) {
                left++;
            }
            else {
                right--;
            }
        }
        return res;
    }
}

补充说明：

• 这里是牛客编码链接