剑指42-和为S的两个数

滑窗、双指针

题目描述

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

输出描述

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

和剑指41题类似

解法1

滑窗

定义两个指针，一个在头，一个在尾

进入循环，左指针不超过右指针

当前和小于sum时，左指针右移，当前和大于sum时，右指针左移，如果西昂等，继续判断乘积

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> res;
        int l=0, r=array.size()-1;
        int mul=INT_MAX;
        while(l<r)
        {
            if(array[l]+array[r]<sum)
            {
                l++;
            }
            else if(array[l]+array[r]>sum)
            {
                r--;
            }
            else
            {
                if(array[l]*array[r]<mul) {
                    mul=array[l]*array[r];
                    res={array[l], array[r]};
                }
                l++;
                r--;
            }
        }
        return res;

    }
};

解法2

双指针：

其实这个和解法1都是双指针，不过不同的是，这里两个指针起点相邻

而且这里复杂度为o(n^2)

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> res;
        int l=0, r=array.size()-1;
        int mul=INT_MAX;
        for(int l=0;l<array.size();l++)
        {
            for(int r=l+1;r<array.size();r++)
            {
                if(array[l]+array[r]<sum)
                {
                    continue;
                }
                else if(array[l]+array[r]>sum)
                {
                    break;
                }
                else 
                {
                    if(array[l]*array[r]<mul)
                    {
                        mul=array[l]*array[r];
                        res={array[l], array[r]};
                    }
                }
            }
        }

        return res;
    }
};