leetcode-0015

题目：

三数之和

关键词：

排序 二分法查找

#include <stdio.h>
#include <stdlib.h>

static int CmpMinor(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

// static int CmpMajor(const void *a, const void *b)
// {
//     return *(int *)b - *(int *)a;
// }

void PutArrayInorder(int *array, int size)
{
    if (array == NULL) {
        printf("[%s_%d]array is null\n", __func__, __LINE__);
        return;
    }
    if (size <= 0) {
        printf("[%s_%d]size is %d\n", __func__, __LINE__, size);
        return;
    }
    qsort(array, size, sizeof(int), CmpMinor);
}

static int halfIntervalSearch(int *array, int const size, const int val)
{
    if (array == NULL) {
        printf("[%s_%d]array is null\n", __func__, __LINE__);
        return -1;
    }
    if (size <= 1) {
        if ((size == 1) && (array[0] == val)) {
            return 0;
        }
        // printf("[%s_%d]size is %d\n", __func__, __LINE__, size);
        return -1;
    }
    int middleOffset = size / 2;
    int middleVal = array[middleOffset];
    
    // printf("[%s_%d]middleOffset=%d, size=%d, middleVal=%d\n", __func__, __LINE__, middleOffset, size, middleVal);
    if (val == middleVal) {
        return middleOffset;
    } else if (val > middleVal) {
        return halfIntervalSearch(&array[middleOffset], size - middleOffset, val);
    } else {
        return halfIntervalSearch(&array[0], size - middleOffset, val);
    }
}

int searchAarrayVal(int *array, int size, int val)
{
    if (array == NULL) {
        printf("[%s_%d]array is null\n", __func__, __LINE__);
        return -1;
    }
    if (size <= 0) {
        printf("[%s_%d]size is %d\n", __func__, __LINE__, size);
        return -1;
    }
    int ret = halfIntervalSearch(array, size, val);
    return ret;
}
/**
 * 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** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
    int i, j;
    *returnSize = 0;
    if (numsSize < 3) {
        return NULL;
    }
    PutArrayInorder(nums, numsSize);
    int maxRow = numsSize * numsSize;
    int **arrayPtr = (int **)malloc(maxRow);
    if (arrayPtr == NULL) {
        return NULL;
    }
    int *columnSizes = (int *)malloc(sizeof(int) * maxRow);
    if (columnSizes == NULL) {
        free(arrayPtr);
        return NULL;
    }
    int cnt = 0;
    int ret;
    for (i = 0; i < numsSize - 2; i++) {
        if (nums[i] > 0) {
            // printf("nums[%d]=%d, nums[i+1]=%d, out of value range\n", i, nums[i], nums[i + 1]);
            break;
        }
        for (j = i + 1; j < numsSize - 1; j++) {
            if (nums[i] + nums[j] > 0) {
                // printf("out of value range\n");
                break;
            }
            ret = searchAarrayVal(&nums[j + 1], numsSize - j - 1, -(nums[i] + nums[j]));
            if (ret < 0) {
                // printf("not found\n");
                continue;
            }
            arrayPtr[cnt] = (int *)malloc(sizeof(int) * 3);
            if (arrayPtr[cnt] == NULL) {
                printf("malloc error\n");
                break;
            }
            arrayPtr[cnt][0] = nums[i];
            arrayPtr[cnt][1] = nums[j];
            arrayPtr[cnt][2] = -(nums[i] + nums[j]);
            // printf("cnt=%d, nums[%d]=%d, nums[%d]=%d, arrayPtr[][2]=%d\n", cnt, i, nums[i], j, nums[j], ret);
            columnSizes[cnt] = 3;
            cnt++;
            while ((j < numsSize - 2) && (nums[j] == nums[j + 1])) {
                j++;
            }
        }
        if (nums[numsSize - 1] - nums[0] < 1) {
            break;
        }
        while ((i < numsSize - 2) && (nums[i] == nums[i + 1])) {
            i++;
        }
    }
    // printf("cnt=%d\n", cnt);
    *returnSize = cnt;
    // printf("*returnSize=%d\n", *returnSize);
    *returnColumnSizes = columnSizes;
    // printf("*returnColumnSizes=%p\n", *returnColumnSizes);
    return arrayPtr;
}