leetcode Two Sum-白红宇

leetcode Two Sum

阅读量：5901 次

发布时间：2019-06-19

本文共 1880 字，大约阅读时间需要 6 分钟。

PS:下面贴的这个代码是二分查找的那个，不是那个用map的我再写一遍吧。

map代码：

#include#include
      
       #include
       
        using namespace std;vector
        
          TwoSum(vector
         
           numbers, int target){    vector
          
            result; map
           
             hmap; for (int i = 0; i < numbers.size(); i++) { int x = target - numbers[i]; if (hmap.count(x) == 0) { hmap.insert(pair
            
             (numbers[i], i)); } else { int j = hmap[x]; result.push_back(j + 1); result.push_back(i + 1); return result; } } return result;}int main(){ vector
             
               a = { 2, 7, 13, 4 }; vector
              
                b = TwoSum(a, 9); for (int i = 0; i < 2; i++) { cout << b[i] << " "; }}

PS： STL真的很好用啊！！！！

本来这个题呢，是O(n2)但是试了一下，没过，这个在预期内！！然后想到了，查找target-a[i]这种方法，排序要O(nlgn)，后来仔细一想，我还要保存排序前的的数组下表，而且这好像也不像算法OJ的考察方式吧。然后找了下答案，最后发现其实和我保存的方式差不多，只不过，别人利用map把search target-a[i] 的时间降到了O(1)时间，这就是用stl的好处。

二分查找代码：

1 class Solution { 2 public: 3     vector
     
       twoSum(vector
      
        &numbers, int target) { 4         sort(numbers.begin(),numbers.end()); 5     int size = numbers.size(); 6     vector
       
         result; 7     for (int i = 0; i < size; i++) 8     { 9         int t = target - numbers[i];10         int p = i + 1; 11         int r = size - 1;12         int q = (p+r) / 2;13         int j = i;14         while (p <= r)15         {16             if (numbers[q] == t)17             {18                 j = q;19                 break;20             }21             if (t
        
          i)33         {34             result.push_back(i + 1);35             result.push_back(j + 1);36             return result;37         }38     }39     return result;40     }41 };

转载于:https://www.cnblogs.com/chaiwentao/p/4313836.html

你可能感兴趣的文章

Tomcat的设置4——Tomcat的体系结构与设置基于端口号的虚拟主机