每周一道算法题(十四)

本周题目难度级别Medium,但对于我来说是低于easy的,据说《剑指offer》中也有这道题。。。

题目:找出一组集合中的四个数，要求四个数的和等于target，不能有重复

看了题目就想到之前有一道从集合中找三个数，要求等于‘0’，不能有重复，我还做超时了，这次的题目就是改改代码么，所以对我来说难度级别就低于easy了，事实上我也就用了几分钟就通过了这道题，虽然效率不高。可以对比着那道题一起看传送门，下面直接上代码：

/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
 //排序
 void quickSort(int* nums,int first,int end){
    int temp,l,r;
    if(first>=end)return;
    temp=nums[first];
    l=first;r=end;
    while(l<r){
        while(l<r && nums[r]>=temp)r--;
        if(l<r)nums[l]=nums[r];
        while(l<r && nums[l]<=temp)l++;
        if(l<r)nums[r]=nums[l];
    }
    nums[l]=temp;
    quickSort(nums,first,l-1);
    quickSort(nums,l+1,end);
}

int** fourSum(int* nums, int numsSize, int target, int* returnSize) {
    //给的集合个数小于4,直接返回0
    if (numsSize < 4) {
        *returnSize = 0;
        return 0;
    }
    //排序
    quickSort(nums,0,numsSize-1);
    //定义链表
    struct Node {
        int data[4];
        struct Node *next;
    }node;
    struct Node *head, *p, *pt;
    int len = 0;
    head = (struct Node *)malloc(sizeof(node));
    head->next = NULL;
    p = head;
    //找出符合条件的四个数，并用链表记录
    for (int i = 0;i < numsSize - 3;i++) {
        for (int j = i+1;j < numsSize - 2;j++) {
            if (i == j) j++;
            if  (j >= (numsSize - 2)) break;
            for (int k = j+1;k < numsSize - 1;k++) {
                while (k == i || k == j) k++;
                if (k >= (numsSize-1)) break;
                for (int l = k+1;l <numsSize;l++) {
                    while (l == i || l == j || l== k) l++;
                    if (l >= numsSize) break;
                    if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
                        //记录长度
                    len++;
                    //将排序好的组合通过链表记录
                    pt = (struct Node *)malloc(sizeof(node));
                    pt->data[0] = nums[i];
                    pt->data[1] = nums[j];
                    pt->data[2] = nums[k];
                    pt->data[3] = nums[l];
                    pt->next = NULL;
                    p->next = pt;
                    p = pt;
                    }
                }
            }
        }
    }
    //删除重复的组合
    p = head->next; 
    struct Node *pre;
    while(p != NULL) {
        pre = p;
        while(pre->next != NULL) {
            if(pre->next->data[0] == p->data[0] && pre->next->data[1] == p->data[1] && pre->next->data[2] == p->data[2]) {
                pt = pre->next; 
                pre->next = pt->next;   
                free(pt);
                len--;//记录长度
            }else pre = pre->next;
        }
        p = p->next;
    }
    
    //将最后的结果整理返回
    *returnSize = len;
    p = head->next;
    int **returnPtr = malloc(sizeof(int*) *len);
    int x = 0;
    while (p != NULL) {
        int *arr = malloc(sizeof(int) *4);
        for (int i = 0;i < 4;i++)
            arr[i] = p->data[i];
        returnPtr[x++] = arr;
        p = p->next;
    }
    return returnPtr;
}

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!