leetcode 1 Two Sum

solution1:

 1 class Solution {
 2 public:
 3         struct pair{
 4                 std::vector<int>* v;
 5                 int i;
 6 
 7                 bool operator < (const pair &a) const{
 8                         return (*v)[i] > (*a.v)[a.i];
 9                 }
10         };
11 
12     std::vector<int> twoSum(std::vector<int>& nums, int target) {
13         std::vector<pair> nums2;
14         std::vector<int> ret;
15         sort(nums, nums2);
16         int ns = nums.size();
17         for(int i=0; i<ns-1; ++i){
18                 int tmp = target - nums[nums2[i].i];
19                 for(int j=i+1; j<ns; ++j){
20                         if(tmp == nums[nums2[j].i]){
21                                 ret.push_back(nums2[i].i);
22                                 ret.push_back(nums2[j].i);
23                                 std::sort(ret.begin(), ret.end());
24                                 return ret;
25                         }
26                 }
27         }
28         return ret;
29     }
30 
31     void sort(std::vector<int>& nums, std::vector<pair>& nums2){
32         int ns = nums.size();
33         nums2.resize(ns);
34         for(int i=0; i<ns; ++i){
35                 nums2[i].v = &nums;
36                 nums2[i].i = i;
37         }
38 
39         std::sort(nums2.begin(), nums2.end());
40     }
41 };

View Code

solution2:

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int>& nums, int target){
 4         map <int, int> mp;
 5         vector <int> res(2);
 6         int n = nums.size();
 7         for (int i = 0; i < n; i++) {
 8             int another = target - nums[i];
 9             if (mp.count(another)) {
10                 res[0] = mp[another];
11                 res[1] = i;
12                 break;
13             }
14             mp[nums[i]] = i;
15         }
16         return res;
17     }
18 };

View Code

两种方法思路大体相同，第二种更好，一方面使用了stl，代码简单明晰，另一方面，排序并不必要完全进行，利用map内部排序，使得一边排序一边查找，性能最佳。