即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

42、与为S的两个数字

编程语言 buki26 11℃ 0评论

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

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

自己的思路是正确的,通过上一题的双指针演化而来,然鹅。。细节方面的问题调了好久。。。

思路:定义两个指针,指向第一个和最后一个,判断和,小于第一个指针后移,大于则第二个指针前移。

代码:

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        if(array.size()==0)
            return vector<int>();
        vector<vector<int> > candidates;
        vector<int> res(2);
        int mulres = array[array.size()-1] * array[array.size()-1];
        int i = 0;
        int j = array.size()-1;
        while(i < j){           
            if(array[i]+array[j]==sum){
                if(array[i]*array[j] < mulres){
                    res[0] = array[i];
                    res[1] = array[j]; 
                    mulres = array[i]*array[j];              
                }
                //这里的i和j自加自减不加要陷入死循环的
                //以及!!把i和j的自加自减加到上面里层的if里把自己给坑坏了。。。
                i++;
                j--;
            }
            else if(array[i]+array[j] < sum){
                i++;
            }
            else{
                j--;
            }
        }
        if(res[0]+res[1]!=sum)
            return vector<int>();
        return res;
    }
};

转载请注明:CodingBlog » 42、与为S的两个数字

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情