首页 > 代码库 > leetcode-two sum

leetcode-two sum

2024-07-30 08:56:20   220人阅读

之前是通过hash来做，O(n)。这次为了熟悉通用性的解法，通过双指针来做。时间复杂度为O(nlogn)（即sort的复杂度）。

主要是关于sort的用法上不太熟，关于自定义sort规则。

C++ Reference中给的示例代码如下：
 1 // sort algorithm example 2 #include <iostream>     // std::cout 3 #include <algorithm>    // std::sort 4 #include <vector>       // std::vector 5  6 bool myfunction (int i,int j) { return (i<j); } 7  8 struct myclass { 9   bool operator() (int i,int j) { return (i<j);}10 } myobject;11 12 int main () {13   int myints[] = {32,71,12,45,26,80,53,33};14   std::vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 3315 16   // using default comparison (operator <):17   std::sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 3318 19   // using function as comp20   std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)21 22   // using object as comp23   std::sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)24 25   // print out content:26   std::cout << "myvector contains:";27   for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)28     std::cout << ‘ ‘ << *it;29   std::cout << ‘\n‘;30 31   return 0;32 }

从中可以看到除了写compare函数外，还可以通过重载圆括号()来写函数对象。

一开始是写了个compare函数。

bool compare(const Node &lhs, const Node &rhs){      return lhs.val < rhs.val;
}
发现对于leetcode而言貌似只能提交class Solution内部的部分。而compare函数放在Solution内部就会出错，放在Solution外面就正常。为什么？？？
然后就通过重载圆括号写了函数对象，顺利通过。
 1 class Solution {//two sum O(nlogn) 2 public: 3     struct Node{ 4         int val; 5         int index; 6         Node(int v, int idx) :val(v), index(idx){} 7     }; 8     struct myclass { 9         bool operator() (Node n1, Node n2) { return (n1.val<n2.val); }10     } myobject;11 12     vector<int> twoSum(vector<int> &numbers, int target) {13         vector<Node> a;14         for (int i = 0; i < numbers.size(); i++)15         {16             a.push_back(Node(numbers[i], i + 1));17         }18         sort(a.begin(), a.end(),myobject );19         int i = 0, j = numbers.size() - 1;20         vector<int> res;21         while (i < j)22         {23             int sum = a[i].val + a[j].val;24             if (sum == target)25             {26                 int minIndex = min(a[i].index,a[j].index);27                 int maxIndex = max(a[i].index, a[j].index);28                 res.push_back(minIndex);29                 res.push_back(maxIndex);30                 break;31             }32             else if (sum < target)33             {34                 i++;35             }36             else37             {38                 j--;39             }40         }41         return res;42     }43 };

 

leetcode-two sum


联系
我们