Ming
0%

LeetCode-454

Posted on Edited on In

题目

Snipaste_2020-11-27_12-04-10.png

结果

Snipaste_2020-11-27_14-08-06.png

代码

暴力法（超时）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int cnt = 0;
        for (int a : A) {
            for (int b : B) {
                for (int c : C) {
                    for (int d : D) {
                        if (a + b + c + d == 0) {
                            cnt++;
                        }
                    }
                }
            }
        }
        return cnt;
    }
}

暴力法改进（超时）

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
class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        if (A.length == 0) {
            return 0;
        }

        int cnt = 0;
        Arrays.sort(A);
        Arrays.sort(B);
        Arrays.sort(C);
        Arrays.sort(D);

        int aMin = A[0], bMin = B[0], cMin = C[0], dMin = D[0];
        int aMax = A[A.length - 1], bMax = B[B.length - 1], cMax = C[C.length - 1], dMax = D[D.length - 1];


        for (int a : A) {
            if (aMax + bMax + cMax + dMax < 0 || aMin + bMin + cMin + dMin > 0) {
                break;
            }
            if (a + bMin + cMin + dMin > 0) {
                break;
            }
            for (int b : B) {
                if (a + bMax + cMax + dMax < 0 || a + bMin + cMin + dMin > 0) {
                    break;
                }
                if (a + b + cMin + dMin > 0) {
                    break;
                }
                for (int c : C) {
                    if (a + b + cMax + dMax < 0 || a + b + cMin + dMin > 0) {
                        break;
                    }
                    if (a + b + c + dMin > 0) {
                        break;
                    }
                    for (int d : D) {
                        if (a + b + c + dMax < 0 || a + b + c + dMin > 0) {
                            break;
                        }
                        if (a + b + c + d == 0) {
                            cnt++;
                        }
                        if (a + b + c + d > 0) {
                            break;
                        }
                    }
                }
            }
        }
        return cnt;
    }
}

借助HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int cnt = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int a : A) {
            for (int b : B) {
                map.put(a + b, map.getOrDefault(a + b, 0) + 1);
            }
        }
        for (int c : C) {
            for (int d : D) {
                if (map.containsKey(-c - d)) {
                    cnt += map.get(-c - d);
                }
            }
        }
        return cnt;
    }
}

空间换时间。

复杂度

时间复杂度：O（N²）

空间复杂度：O（N²）