数组中查找和正好是S的两个数,代码实现和思路

KLQ 2020-04-15 14:53:39 java常见问答 4330

下面要给大家带来的是和为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实例专栏了解。