下面要给大家带来的是和为S的两个数字的代码实现和思路，具体的包括了3种代码实现和思路整理，希望可以对大家有帮助。

题目：

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

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

思路1：

数列满足递增，设两个头尾两个指针i和j，

1、假如ai+aj==sum，就是答案(相差越远乘积越小)

2、假如ai+aj> sum，aj肯定不是答案之一(前面已经得出了i前面的数已经是不可能)，j-=1

2、假如ai+aj< sum，ai肯定不是答案之一(前面已经得出了j后面的数已经是不可能)，i+=1

O(n)

代码实现：

typedef vector < int > vi;
class Solution
{
    public:
        vi FindNumbersWithSum(const vi & a, int sum)
        {
            vi res;
            int n = a.size();
            int i = 0, j = n - 1;
            while (i < j)
            {
                if (a[i] + a[j] == sum)
                {
                    res.push_back(a[i]);
                    res.push_back(a[j]);
                    break;
                }
                while (i < j && a[i] + a[j] > sum) --j;
                while (i < j && a[i] + a[j] < sum) ++i;
            }
            return res;
        }
};

思路2：

排序的话，那么非常的好处理：左右加逼

代码实现：

import java.util.ArrayList;
public class Solution
{
    public ArrayList < Integer > FindNumbersWithSum(int[] array, int sum)
    {
        ArrayList < Integer > list = new ArrayList < Integer > ();
        if (array == null || array.length < 2)
        {
            return list;
        }
        int i = 0, j = array.length - 1;
        while (i < j)
        {
            if (array[i] + array[j] == sum)
            {
                list.add(array[i]);
                list.add(array[j]);
                return list;
            }
            else if (array[i] + array[j] > sum)
            {
                j--;
            }
            else
            {
                i++;
            }
        }
        return list;
    }
}

思路3：

不要被题目误导啦!看下面!

输出两个数的乘积最小的。这句话的理解?

假设：若b>a,且存在，

a + b = s;

(a - m ) + (b + m) = s

则：(a - m )(b + m)=ab - (b-a)m - m*m < ab;说明外层的乘积更小

也就是说依然是左右夹逼法，只需要2个指针

一、left开头，right指向结尾

二、假如和小于sum，说明太小了，left右移寻找更大的数

三、假如和大于sum，说明太大了，right左移寻找更小的数

四、和相等，把left和right的数返回

代码实现：

public ArrayList < Integer > FindNumbersWithSum(int[] array, int sum)
{
    ArrayList < Integer > list = new ArrayList < > ();
    if (array == null || array.length == 0)
        return list;
    int left = 0;
    int right = array.length - 1;
    while (left < right)
    {
        int total = array[left] + array[right];
        if (total == sum)
        {
            list.add(array[left]);
            list.add(array[right]);
            return list;
        }
        else if (total > sum)
        {
            //大于sum，说明太大了，right左移寻找更小的数
            --right;
        }
        else
        {
            //2.如果和小于sum，说明太小了，left右移寻找更大的数
            ++left;
        }
    }
    return list;
}

能够实现的代码和思路远远不止这些，更多的Java实例，大家可以继续的关注本站的Java实例专栏了解。