Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.
Example:
- Input: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2]
- Output: 2
- The two tuples are:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
C Solution:
struct He {
int val;
int count;
struct He *next;
};
struct Ht {
int size;
struct He **list;
};
struct Ht *create() {
struct Ht *ht = malloc(sizeof(struct Ht));
ht->size = 12345;
ht->list = calloc(ht->size, sizeof(struct He *));
return ht;
}
void insert(struct Ht *ht, int val) {
int ind = val % ht->size;
if (ind < 0) ind = -ind;
struct He *p = ht->list[ind];
while (p) {
if (p->val == val) {
p->count++;
return;
}
p = p->next;
}
p = malloc(sizeof(struct He));
p->val = val;
p->count = 1;
p->next = ht->list[ind];
ht->list[ind] = p;
}
int find(struct Ht *ht, int val) {
int ind = val % ht->size;
if (ind < 0) ind = -ind;
struct He *p = ht->list[ind];
while (p) {
if (p->val == val) {
return p->count;
}
p = p->next;
}
return 0;
}
int fourSumCount(int* A, int ASize, int* B, int BSize, int* C, int CSize, int* D, int DSize) {
struct Ht *ht = create();
int i, j;
for (i = 0; i < ASize; i++) {
for (j = 0; j < BSize; j++) {
insert(ht, A[i] + B[j]);
}
}
int res = 0;
for (i = 0; i < CSize; i++) {
for (j = 0; j < DSize; j++) {
res += find(ht, -C[i] - D[j]);
}
}
return res;
}
Summary:
- If
ht->size == 1234, TLE. - If
ht->size == 12345, 895ms, 0%. - If
ht->size == 123456, 118ms, 100%. - tradeoff between space and time.
- This is not similar to 4Sum, actually.
LeetCode: 454. 4Sum II
近期评论