题目描述

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

题目解读

• 剑指Offer 280

代码

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int length = array.size();
        int left = 0;
        int right = length - 1;
        vector<int> data;

        while(left < right){
            int toSum = array[left] + array[right];
            if(toSum == sum){
                data.push_back(array[left]);
                data.push_back(array[right]);
                break;
            }
            else if(toSum > sum){
                right --;
            }
            else{
                left ++;
            }
        }
        return data;
    }
};


int main(){
    int a[10] = {1, 2, 4, 7, 8, 11, 15};
    int len = 7;
    
    vector<int> array;
    Solution ss;

    for(int i=0; i < len; i++){
        array.push_back(a[i]);
    }

    vector<int> data = ss.FindNumbersWithSum(array, 15);
    for(int i=0; i < data.size(); i++){
        cout<<data[i]<<endl;
    }
}

总结展望

• 这道题目在剑指Offer上面是随意输出一个符合条件的两个数就行，但是在牛客上是输出所有符合条件中乘积最小的两个数，然后，仔细一观察，按照剑指Offer上方法求解出来的最边缘的两个数可不是就是乘积最小的两个数.
• 一般题目瞬间就想出来的是效率低的方式，好的方法需要多加练习 -> 刷题