18. 4Sum，四数和

Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        size = len(nums)
        if size < 4:
            return []
        nums.sort()
        if sum(nums[:4])>target or sum(nums[-4:])<target:
            return []
        r = []
        for i in range(size-3):
            if(i>0 and nums[i]==nums[i-1]):
                continue
            for j in range(i+1,size-2):
                if(j>i+1 and nums[j]==nums[j-1]):
                    continue
                t = target - nums[i] - nums[j]
                lo = j + 1
                hi = size - 1
                while lo < hi:
                    s = nums[lo] + nums[hi]
                    if s<t or (lo>j+1 and nums[lo]==nums[lo-1]):
                        lo += 1
                        continue
                    if s>t or (hi<size-1 and nums[hi]==nums[hi+1]):
                        hi -= 1
                        continue
                    r.append((nums[i],nums[j],nums[lo],nums[hi]))
                    lo += 1
                    hi -= 1
        return r

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        r = []
        nc = Counter(nums)
        nsorted = sorted(nc)
        size = len(nsorted)
        # four identicals
        if target % 4 == 0:
            d4 = target // 4
            if nc[d4] >= 4:
                r.append([d4,d4,d4,d4])
        # three identicals
        for n,c in nc.items():
            d3 = target - n*3
            if c>=3 and nc[d3] and d3!=n:
                r.append([n,n,n,d3])
        # two of two identicals
        n2 = sorted([n for n,c in nc.items() if c>=2])
        n2size = len(n2)
        left = 0
        right = n2size - 1
        while left < right:
            s = n2[left]*2 + n2[right]*2
            if s == target:
                r.append([n2[left],n2[left],n2[right],n2[right]])
                left += 1
                right -= 1
                continue
            if s < target:
                left += 1
            else:
                right -= 1
        # two identicals and two different
        for n,c in nc.items():
            if c >= 2:
                t = target - n*2
                left = 0
                right = size - 1
                while left < right:
                    if nsorted[left] == n:
                        left += 1
                        continue
                    if nsorted[right] == n:
                        right -= 1
                        continue
                    s = nsorted[left] + nsorted[right]
                    if s == t:
                        r.append([n,n,nsorted[left],nsorted[right]])
                        left += 1
                        right -= 1
                        continue
                    if s < t:
                        left += 1
                    else:
                        right -= 1
        # four different
        if (sum(nsorted[:4])>target
                or sum(nsorted[-4:])<target):
            return r
        for i in range(size-2):
            for j in range(i+1,size-1):
                for k in range(j+1,size):
                    t = target - nsorted[i] - nsorted[j] - nsorted[k]
                    if nc[t] and nsorted.index(t)>k:
                        r.append([nsorted[i],nsorted[j],nsorted[k],t])
        return r

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        def _kSum(data: list[int], k: int, target: int) -> list[list[int]]:
            if not data:
                return []
            mean_target = target // k
            if mean_target<data[0] or mean_target>data[-1]:
                return []
            if k == 1:
                if target in data:
                    return [(target,)]
                return []
            r1 = [it+(data[0],) for it in _kSum(data[1:],k-1,target-data[0])]
            i = 1
            while i<len(data) and data[i]==data[i-1]:
                i += 1
            r2 = [it for it in _kSum(data[i:],k,target)]
            return r1 + r2

        nums.sort()
        return _kSum(nums, 4, target)

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        def _2Sum(data, target):
            r = []
            nm1 = len(data) - 1
            lo = 0
            hi = nm1
            while lo < hi:
                s = data[lo] + data[hi]
                if s<target or (lo>0 and data[lo]==data[lo-1]):
                    lo += 1
                    continue
                if s>target or (hi<nm1 and data[hi]==data[hi+1]):
                    hi -= 1
                    continue
                r.append((data[lo],data[hi]))
                lo += 1
                hi -= 1
            return r

        def _kSum(data: list[int], k: int, target: int) -> list[list[int]]:
            if not data:
                return []
            mt = target // k
            if mt<data[0] or mt>data[-1]:
                return []
            if k == 2:
                return _2Sum(data,target)
            r = []
            for i in range(len(data)):
                if i==0 or data[i]!=data[i-1]:
                    r += [it+(data[i],) for it in _kSum(data[i+1:],k-1,target-data[i])]
            return r

        nums.sort()
        return _kSum(nums, 4, target)

class Solution {
    using rtype = vector<vector<int>>;

    rtype _2Sum(vector<int> &data, size_t sidx, long long target){
        rtype r;
        size_t sizep1 { data.size()-1 };
        size_t lo { sidx };
        size_t hi { sizep1 };
        while(lo < hi){
            long long s { data[lo]+data[hi] };
            if(s<target || (lo>sidx && data[lo]==data[lo-1])){
                ++lo;
                continue;
            }
            if(s>target || (hi<sizep1 && data[hi]==data[hi+1])){
                --hi;
                continue;
            }
            r.push_back({data[lo],data[hi]});
            ++lo;
            --hi;
        }
        return r;
    }

    rtype kSum(vector<int> &data, size_t sidx, int k, long long target){
        rtype r;
        if(data.size()-sidx < k)
            return r;
        long long m { target/k };
        if(m<data[sidx] || m>data.back())
            return r;
        if(k == 2)
            return _2Sum(data, sidx, target);
        for(size_t i{sidx}; i<data.size()-k+1; ++i){
            if(i==sidx || data[i]!=data[i-1]){
                rtype m { kSum(data,i+1,k-1,target-data[i]) };
                for(auto it: m){
                    it.push_back(data[i]);
                    r.push_back(it);
                }
            }
        }
        return r;
    }

public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        return kSum(nums, 0, 4, target);
    }
};

static int cmp(const void *a, const void *b){
    // constraints tell me there is no possible to overflow
    return *(int*)a - *(int*)b;
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){
    if(numsSize < 4){
        *returnSize = 0;
        *returnColumnSizes = NULL;
        return NULL;
    }
    qsort(nums, numsSize, sizeof(int), cmp);
    long long smallest = (long long)nums[0]+nums[1]+nums[2]+nums[3];
    long long biggest = (long long)nums[numsSize-1]+nums[numsSize-2]+nums[numsSize-3]+nums[numsSize-4];
    if(smallest>target || biggest<target){
        *returnSize = 0;
        *returnColumnSizes = NULL;
        return NULL;
    }
    int **r = NULL;
    int ridx = 0;
    for(int i=0; i<numsSize-3; ++i){
        if(i>0 && nums[i]==nums[i-1])
            continue;
        for(int j=i+1; j<numsSize-2; ++j){
            if(j>i+1 && nums[j]==nums[j-1])
                continue;
            long long t = (long long)target - nums[i] - nums[j];
            int lo = j + 1;
            int hi = numsSize - 1;
            while(lo < hi){
                long long s = nums[lo] + nums[hi];
                if(s<t || (lo>j+1 && nums[lo]==nums[lo-1])){
                    ++lo; continue;
                }
                if(s>t || (hi<numsSize-1 && nums[hi]==nums[hi+1])){
                    --hi; continue;
                }
                if(ridx%64 == 0)
                    r = realloc(r, sizeof(int*)*(ridx/64+1)*64);
                r[ridx] = malloc(sizeof(int)*4);
                r[ridx][0] = nums[i];
                r[ridx][1] = nums[j];
                r[ridx][2] = nums[lo];
                r[ridx++][3] = nums[hi];
                ++lo; --hi;
            }
        }
    }
    r = realloc(r, sizeof(int*)*ridx);
    *returnSize = ridx;
    *returnColumnSizes = malloc(sizeof(int)*ridx);
    for(int i=0; i<ridx; ++i)
        (*returnColumnSizes)[i] = 4;
    return r;
}

static int cmp(const void *a, const void *b){
    // constraints tell me there is no possible to overflow
    return *(int*)a - *(int*)b;
}

static int origin_k = 0;
static int **r = NULL;
static int ridx = 0;

static int _2Sum(int *data, int size, long long t){
    int nfind = 0;
    int lo = 0;
    int hi = size - 1;
    while(lo < hi){
        long long s = data[lo] + data[hi];
        if(s<t || (lo>0 && data[lo]==data[lo-1])){
            ++lo; continue;
        }
        if(s>t || (hi<size-1 && data[hi]==data[hi+1])){
            --hi; continue;
        }
        if(ridx%64 == 0)
            r = realloc(r, sizeof(int*)*(ridx/64+1)*64);
        r[ridx] = malloc(sizeof(int)*origin_k);
        r[ridx][0] = data[lo];
        r[ridx++][1] = data[hi];
        ++lo;
        --hi;
        ++nfind;
    }
    return nfind;
}

static int kSum(int *data, int size, int k, long long target, int *sidx){
    if(size < k)
        return 0;
    long long mt = target / k;
    if(data[0]>mt || data[size-1]<mt)
        return 0;
    if(k == 2)
        return _2Sum(data,size,target);
    int tfind = 0;
    int nfind = 0;
    int km1 = k - 1;
    for(int i=0; i<=size-k; ++i){
        if(i==0 || data[i]!=data[i-1]){
            tfind = kSum(data+i+1,size-i-1,km1,target-data[i],sidx);
            for(int j=sidx[km1]; j<sidx[km1]+tfind; ++j)
                r[j][km1] = data[i];
            sidx[km1] += tfind;
            nfind += tfind;
        }
    }
    return nfind;
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){
    if(numsSize < 4){
        *returnSize = 0;
        *returnColumnSizes = NULL;
        return NULL;
    }

    qsort(nums, numsSize, sizeof(int), cmp);

    origin_k = 4;
    int sidx[origin_k];
    memset(sidx, 0, sizeof(int)*origin_k);
    ridx = 0;
    kSum(nums, numsSize, 4, target, sidx);

    r = realloc(r, sizeof(int*)*ridx);
    *returnSize = ridx;
    *returnColumnSizes = malloc(sizeof(int)*ridx);
    for(int i=0; i<ridx; ++i)
        (*returnColumnSizes)[i] = 4;
    return r;
}