Accepted as best submission in C enclosed with clear comments


  • 0
    void sort(int* nums, int begin, int end)
    {
        int l=begin, r=end;
        int v = nums[l+(r-l)/2];
        while(l <= r)
        {
            while(nums[l] < v) l++;
            while(nums[r] > v) r--;
            if(l <= r)
            {
                int t = nums[l];
                nums[l] = nums[r];
                nums[r] = t;
                l++; r--;
            }
        }
        if(r > begin)
            sort(nums, begin, r);
        if(l < end)
            sort(nums, l, end);
    }
    
    //AC - 24ms;
    int** threeSum(int* nums, int size, int* returnSize)
    {
        sort(nums, 0, size-1);
        int left, right;
        int** arr = (int**)malloc(sizeof(int*));
        *returnSize = 0;
        for(int i = 0; i < size-2; i++)
        {
            while(i<size-2 && i>0 && nums[i]==nums[i-1]) i++; //avoid redundant traversal by isolating the duplicates;
            left = i+1;
            right = size-1;
            int sum = -nums[i];
            while(left < right) //the searching process is the same with the 2-sum problem;
            {
                int t = nums[left]+nums[right];
                if(t > sum) right--;
                else if(t < sum) left++;
                else
                {
                    if(!*returnSize || (*returnSize && (nums[i]!=arr[*returnSize-1][0] ||
                                    nums[left]!=arr[*returnSize-1][1]))) //collect the qualified and isolating the duplicates;
                    {
                        *returnSize += 1;
                        arr = (int**)realloc(arr, sizeof(int*)*(*returnSize));
                        arr[*returnSize-1] = (int*)malloc(sizeof(int)*3);
                        arr[*returnSize-1][0] = nums[i];
                        arr[*returnSize-1][1] = nums[left];
                        arr[*returnSize-1][2] = nums[right];
                    }
                    left++;
                }
            }
        }
        return arr;
    }

Log in to reply
 

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