leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0018.cpp (1108B)

      1 class Solution {
      2   public:
      3     vector<vector<int>> fourSum(vector<int> &nums, int target) {
      4         vector<vector<int>> res;
      5         int n = nums.size();
      6 
      7         sort(nums.begin(), nums.end());
      8         for (int i = 0; i < n; i++) {
      9             for (int j = i + 1; j < n; j++) {
     10                 long long goal = (long long)target - nums[i] - nums[j];
     11                 int k = j + 1, l = n - 1;
     12                 while (k < l) {
     13                     long long crnt = nums[k] + nums[l];
     14                     if (crnt > goal)
     15                         l--;
     16                     else if (crnt < goal)
     17                         k++;
     18                     else {
     19                         res.push_back({nums[i], nums[j], nums[k], nums[l]});
     20                         k++, l--;
     21                         while (k < l && nums[l] == nums[l + 1])
     22                             l--;
     23                     }
     24                 }
     25                 while (j + 1 < n && nums[j] == nums[j + 1])
     26                     ++j;
     27             }
     28             while (i + 1 < n && nums[i] == nums[i + 1])
     29                 ++i;
     30         }
     31         return res;
     32     }
     33 };