4/02/2014

Leetcode -- 3Sum

class Solution {  
 public:  
   vector<vector<int> > threeSum(vector<int> &num) {  
     std::sort(num.begin(), num.end());  
     int n = num.size();  
     vector<vector<int> > result;  
     if(n < 3){  
       return result;  
     }  
     for(int i = n - 1; i >= 1; i--) {  
          if(i < n - 1 &&num[i] ==num[i+1]) {  // didn't have this previously, so Output Limit Exceed
     continue;  
    }  
       int target = -num[i];  
       vector<vector<int> > temp(twoSum(num, 0, i - 1, target));  
       for(auto& item : temp) {  
         item.emplace_back(num[i]);  
         result.emplace_back(item);  
       }  
     }  
     return result;  
   }  
   vector<vector<int> > twoSum(const vector<int>& num, int start, int end, int target) {  
     vector<vector<int> > result;  
     while(start < end) {  
       int sum = num[start] + num[end];  
       if (sum > target) {  
         while(num[end] == num[--end]);  
       } else if (sum == target) {  
         vector<int> found{num[start], num[end]};  
         result.emplace_back(found);  
         while(num[end] == num[--end]);  
          while(num[start] == num[++start]);  
       } else {  
         while(num[start] == num[++start]);  
       }  
     }  
     return result;  
   }  
 }; 

No comments: