aboutsummaryrefslogtreecommitdiff
path: root/4sum.c
blob: 6c4cfa0ca2ad3e815bdfca3c8e90bb2d4826e5e1 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// 18. 4Sum
#include <stdio.h>
#include <stdlib.h>

/*
 * given array 'nums' of 'n' integers, return an array of all
 * unique qudruplets 'nums[a], nums[b], nums[c], nums[d]'
 * - such that 0 <= a, b, c, d < n
 * - a, b, c, d are distinct
 * - 'nums[a] + nums[b] + nums[c] + nums[d]' == 'target'
 */

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

int **fourSum(int *nums, int numsSize, int target, int *returnSize,
              int **returnColumnsSizes) {
  int i, j, left, right;
  qsort(nums, numsSize, sizeof(int), cmp);
  int **ans = (int **)malloc(1000000 * sizeof(int *));
  int idx = 0;
  for (i = 0; i < numsSize - 3; i++) {
    if (i > 0 && nums[i] == nums[i - 1])
      continue;
    for (j = i + 1; j < numsSize - 2; j++) {
      if (j > i + 1 && nums[j] == nums[j - 1])
        continue;
      left = j + 1;
      right = numsSize - 1;
      while (left < right) {
        long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
        if (sum == target) {
          ans[idx] = (int *)malloc(4 * sizeof(int));
          ans[idx][0] = nums[i];
          ans[idx][1] = nums[j];
          ans[idx][2] = nums[left];
          ans[idx][3] = nums[right];
          idx++;
          left++;
          right--;
          while (left < right && nums[left] == nums[left - 1])
            left++;
          while (right > left && nums[right] == nums[right + 1])
            right--;
        } else if (sum > target)
          right--;
        else
          left++;
      }
    }
  }
  ans = (int **)realloc(ans, idx * sizeof(int *));
  *returnSize = idx;
  returnColumnsSizes[0] = (int *)malloc(idx * sizeof(int));
  for (i = 0; i < idx; i++)
    returnColumnsSizes[0][i] = 4;
  return ans;
}

int main() {
  int nums1[] = {1, 0, -1, 0, -2, 2}, nums2[] = {2, 2, 2, 2, 2};
  int retSz1[] = {3}, retSz2[] = {1};
  int retColSz1[][3] = {}, retColSz2[][1] = {};
  printf("%d\n", fourSum(nums1, 6, 0, retSz1, retColSz1));
}