果然是好久没有刷oj了感觉脑子都不转了 希望在这段时间乃至以后每天都能刷一刷 你看到的别人的辉煌都是付出了一定努力的 我也得花时间才行
首先第一题two sum 对于题目和输出格式困惑了很久
题目要求：给定一个整形的数组和target 能且仅能从数组中找到两个元素相加等于target 返回这两个元素的索引值
输出格式：我还想着要不要写main什么的 事实证明那些东西其实和算法本身无甚关系了 就在给定的方法中码就好
首次尝试：暴力暴力暴力 最直观的解法 时间复杂度O(n2)
改进：看了一些vote最多的解法和别人的博客 其实可以将双层遍历转化为查找 因为题目设置很完美 一定有这么两个元素相加等于target 所以可以从第一个元素开始 计算target-array[0]的值 再在数组中查找这个值 找到了就return 没找到就继续遍历数组 这样粗略来讲只需要遍历一次数组 然后可以优化的地方就在于每一次循环中的查找 可以先排序再查找最好是快排O(nlogn) or 用一种更好的查找方法——使用c++的map 关联类容器
map的查找时间复杂度基本是O(N)，所以这样实现的话时间复杂度基本是O(N) 超棒的！
网友评论