题解 | #和为S的两个数字#

和为S的两个数字

http://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b

模仿#和为S的连续数列#中双指针的思路。
使用左右两个指针,左指针left从数组最左侧开始,右指针right从数组最右侧开始。
计算左右两个指针所指向的值的和,若该和大于sum,则left++,若该和小于sum,则right--。
直到左右指针之和等于sum,此时找到结果;或左右指针指向同一位置,此时无结果,终止循环。

这种做法最多只用遍历一遍数组,时间复杂度为O(n),不借用辅助数组,空间复杂度为O(1)。
但是要吐槽的是,实际运行时间极慢,全部用例使用了20ms,仅打败0.3%的用户。空间复杂度也不尽人意。看了下大家做的也基本都是双指针向中间逼近的,希望有能之士能给点优化的方法及建议。

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> res;
        if(array.empty()){
            return res;
        }
        int left = 0;
        int right = array.size() - 1;
        while(right != left){
            int s = array.at(left) + array.at(right);
            if(s < sum){
                left++;
            }
            else if(s > sum){
                right--;
            }
            else{
                res.push_back(array.at(left));
                res.push_back(array.at(right));
                break;
            }
        }
        return res;
    }
};
全部评论

相关推荐

白火同学:先说结论,准大三不是特别好找实习,boss沟通300+没有实习是很正常的情况。一是暑期实习时间太短了,二是在这么多准大四都找不到实习,从实习时间和掌握技术层面,企业会优先看他们。 再说简历,其实985本+准大三到这水平的简历也很优秀了,要说的话,项目经历可以再优化一下,可以基本围绕采取STAR原则,分为项目概述、技术架构、技术亮点、实现结果,再发给AI润色一下。 最后说操作,准大三的话,如果想找实习那就多投,不过现在也7月中旬了,时间上已经略晚了。如果7月底实在找不到,也可以多刷点算法,多学点技术,这实习也不至于一定得有,当然有更好。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务