题解 | #两数之和# 详细注释 双超99

两数之和

http://www.nowcoder.com/practice/20ef0972485e41019e39543e8e895b7f

解题思路

哈希。

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int m = numbers.size();//计算数组长
        vector<int> ans;//存储答案
        unordered_map<int, int> numPos;//存储元素位置的哈希表
        for(int i = 0; i < m; i++){
            if(numPos.find(target-numbers[i]) != numPos.end()){//如果找到目标,则返回答案
                int a = min(numPos[numbers[i]], numPos[target-numbers[i]]);
                ans.push_back(a);
                ans.push_back(numPos[target-numbers[a]]);
                return ans;
            }
            numPos[numbers[i]] = i;//没找到填表继续扫描下一个元素
        }
        return ans;
    }
};

时间复杂度:O(N)。N为输入数组长度。

空间复杂度:O(N)。哈希表需要O(N)的空间。

全部评论

相关推荐

有没有佬投这个呀,怎么样呀求问
投递中科院空天信息创新研究院等公司10个岗位
点赞 评论 收藏
分享
05-29 09:02
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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