ReaL simple c++ solution with in-line comments

  • 1
    class Solution {
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int>> ans;
            int len=nums.size();
            if (len < 4) return ans; // you want 4-sum, right?
            /* idea: travers first and second numbers, then use o(n) to find third and fourth numbers 
               o(n) algorithm: when array is sorted, let c=0, d=len-1. if n[c]+n[d]<target, we know n[d] can never be 
                    answer, since n[c] is alreayd smallest but the sum is still > target. similarly, when sum>target, c+=1. 
            sort(nums.begin(), nums.end());
            for (int a=0; a<len-3; next_diff(nums, a))
                for (int b=a+1; b<len-2; next_diff(nums, b)) {
                    int c=b+1, d=len-1;
                    int tar=target-nums[a]-nums[b];
                    while (c<d) {
                        int sum=nums[c]+nums[d];
                        if (sum>tar)
                            prev_diff(nums, d);
                        else if (sum<tar)
                            next_diff(nums, c);
                        else {
                            vector<int> sub;
                            prev_diff(nums, d);
                            next_diff(nums, c);
            return ans;
        /* to remove duplicate answers: */
        void next_diff(vector<int>& nums, int& p) {
            int val=nums[p++]; 
            while (p<nums.size())
                if (nums[p]==val) p++;
                else break;
        void prev_diff(vector<int>& nums, int& p) {
            int val=nums[p--];
            while (p>=0)
                if (nums[p]==val) p--;
                else break;

Log in to reply

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