题解 | #和为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;
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-17 14:38
干个蛋,干不了一点!!!!我真服了,还没搞完,很急。&nbsp;今天ddl,活没干完直接通宵,刺激。食堂很好吃,感觉离职的时候会胖10斤。mt喜欢能直接干活的,没空指导我,很难受。每个人都是笑嘻嘻的,但是从他们聊天中都能感受到各种试探,我有点慌了大家真的nb,都能准时完成工作下班,我羡慕啊!!!!!每天好累,想离职了💔
牛客26106072...:能去字节实习说明你的能力挺被认可的,实习中的这种累更有利于个人职场成长,试着当熬夜打游戏一样熬一熬,实习的意义就是看自己的差距和适应能力,总比等到工作时各种不适应辞职要好得多吧?
投递字节跳动等公司9个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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