[15] 3Sum

找加起來等於零
且不可重覆
非常醜我知道 囧
但總之還是先放個初版Orz

3Sum
/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int compare(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

int** threeSum(int* nums, int numsSize, int* returnSize) {
    if (numsSize < 2)
        return NULL;
    qsort(nums,numsSize,sizeof(int),compare);  
    int i,j,k;

    int **ret = malloc(sizeof(int *) * (numsSize*30));
    *returnSize = 0;
    for(i=0;i<numsSize;i++)
    {
        for(j=i+1,k=numsSize-1;j<k;)
        {
            int sum = nums[i]+nums[j]+nums[k] ;
            if(sum < 0)
                j++;
            else if (sum > 0)
                k--;
            else
            {
                int index = *returnSize;
                bool same = false;
                for(int check = index-1; check >=0; check--)
                {
                    if (nums[i]<ret[check][0])
                        break;
                    if (nums[i]==ret[check][0] && nums[j]==ret[check][1] && nums[k]==ret[check][2])
                    {
                        same = true;
                        break;
                    }
                }
                if (same)
                {
                    j++;
                    k--;
                    continue;
                }
                ret[index] = malloc (sizeof(int)*3);
                ret[index][0] = nums[i];
                ret[index][1] = nums[j];
                ret[index][2] = nums[k];
                *returnSize += 1;
                j++;
                k--;
            }
        }
    }
    return ret;
}

但很奇怪後來看別人和我的笨版本差不多意思的卻快很多
為什麼呢 XD
不想研究了 XD
但總之重覆的可以跳過
不曉得為什麼一開始我把重覆的跳過一直不對
所以才弄了笨方法
唉感覺沒天份
以下是跳過重覆的版本
/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int compare(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

int** threeSum(int* nums, int numsSize, int* returnSize) {
    if (numsSize < 2)
        return NULL;
    qsort(nums,numsSize,sizeof(int),compare);  
    int i,j,k;

    int **ret = malloc(sizeof(int *) * (numsSize*30));
    *returnSize = 0;
    for(i=0;i<numsSize;i++)
    {
        if(i>0 && nums[i]==nums[i-1])
            continue;
        for(j=i+1,k=numsSize-1;j<k;)
        {
            int sum = nums[i]+nums[j]+nums[k] ;
            if(sum < 0)
            {
                while(j<k && nums[j]==nums[j+1])
                    j++;
                j++;
            }
            else if (sum > 0)
            {
                while(j<k && nums[k]==nums[k-1])
                    k--;
                k--;
            }
            else
            {
                int index = *returnSize;
                ret[index] = malloc (sizeof(int)*3);
                ret[index][0] = nums[i];
                ret[index][1] = nums[j];
                ret[index][2] = nums[k];
                *returnSize += 1;
                while(j<k && nums[j]==nums[j+1])
                    j++;              
                j++;
                while(j<k && nums[k]==nums[k-1])
                    k--;
                k--;
            }
        }
    }
    return ret;
}

結果修了一下比對的順序, "等於"先做,
然後就笨方法也可以得到很快的結果了 = =
覺得瞎XD
int compare(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

int** threeSum(int* nums, int numsSize, int* returnSize) {
    if (numsSize < 2)
        return NULL;
    qsort(nums,numsSize,sizeof(int),compare);  
    int i,j,k;

    int **ret = malloc(sizeof(int *) * (numsSize*10));
    *returnSize = 0;
    for(i=0;i<numsSize;i++)
    {
        for(j=i+1,k=numsSize-1;j<k;)
        {
            int sum = nums[i]+nums[j]+nums[k] ;
            if (sum==0)
            {
                int index = *returnSize;
                bool same = false;
               
                for(int check = index-1; check >=0; check--)
                {
                    if (nums[i]>ret[check][0])
                        break;
                    else if (nums[i]==ret[check][0] && nums[j]==ret[check][1] && nums[k]==ret[check][2])
                    {
                        same = true;
                        break;
                    }
                }
                if (same)
                {
                    j++;
                    k--;
                    continue;
                }
                ret[index] = malloc (sizeof(int)*3);
                ret[index][0] = nums[i];
                ret[index][1] = nums[j];
                ret[index][2] = nums[k];
                *returnSize += 1;
                j++;
                k--;
            }              
            else if(sum < 0)
                j++;
            else if (sum > 0)
                k--;
        }
    }
    return ret;
}