9ms c++ easy to understand solution


  • 0
    J
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> res;
            int i = 0, last = nums.size() - 1;
            while(i < last) {
              int a = nums[i], j = i + 1;
              if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
              if(nums[i]+nums[last - 2]+nums[last - 1]+nums[last]<target) {
                  i++; 
                  continue;
              }
              while(j < last) {
                int b = nums[j], k = j + 1, m = last;
                if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
                if(nums[i]+nums[j]+nums[last-1]+nums[last]<target) {
                    j++;
                    continue;
                }
                while(k < m) {
                  int c = nums[k], d = nums[m], sum = b + c + d;
                  if(sum == target - a) res.push_back({a, b, c, d});
                  if(sum <= target - a) while(nums[k] == c && k < m) k++;
                  if(sum >= target - a) while(nums[m] == d && k < m) m--; 
                }
                while(nums[j] == b && i < j) j++;
              }
              while(nums[i] == a && i < last) i++;
            }
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.