LeetCode 刷了近 20 道题了，对于我来说，还是有一定的难度的，为了对题目类型及思路有个整体的把握，今天回头看了看这些题目，发现还有很很多相似的地方的，本篇就整理一下，前二十道出现频率最高的求和问题。比如：两数之和等于目标值；三数之和最接近目标值；三数之和为零；四数之和为零。

通用思想

  • 先对数组排序

  • 对于两数，遍历数组，先确定一个数，再从剩下的元素中，从后往前遍历，找到与之之和等于目标值的数

  • 对于三数之和为零，遍历数组，先确定一个数，再从剩下的元素中，找出两个数，使这三数之和为零，找到这两个数的方法， 参考上一条。

  • 对于四叔之和为零，遍历数组，先确定一个数，再从剩下的元素中，找出三个数，使这四数之和为零，找到这三个数的方法， 参考上一条。

  • 对于三数之和最接近目标值，与三数之和类似。不同的是，在每次遍历求和时，记录最接近的值。

关于排序

Java 里面其实给我们提供好了一个方法 Arrays.sort(int[] arr) ，我们可以直接用，但是我本人强烈建议，对于排序算法不熟悉的，可以暂时不用 JDK 提供的，而是去自己实现，尤其是快速排序和归并排序，很多的算法题都需要都需要先排序，借这个可以反复测验的机会，可以极大锻炼我们手写排序算法的能力。

之前也写过几篇文章，介绍几种排序算法，插入排序，归并排序，快速排序，也希望能帮助大家理解。

两数求和（TwoSum）

题目的意思是：找出两个数之和等于目标值的两个数的角标，所以，这里是不可以给元素排序的。根据前面的通用的思想，很容易写出下面的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int[] twoSum(int[] nums, int target) {
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        int end = len - 1;
        while (i < end) {
            int delta = nums[i] + nums[end] - target;
            if (delta != 0) {
                end--;
            } else {
                System.out.println(i + "" + end);
                return new int[]{i, end};
            }
        }
    }
    return new int[]{0, 0};
}

该算法时间复杂度为 O(n²)，空间复杂度为 O(1)。网上还有一种采用 HashMap 实现的方法。时间复杂度为 O(n)，空间复杂度也为 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    int result[] = new int[2];
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(target - nums[i])) {
            result[0] = map.get(target - nums[i]);
            result[1] = i;
        } else {
            map.put(nums[i], i);
        }
    }
    return result;
}

三数之和（3Sum）

将数组中三个数之和为零的所有组合找出放进集合中，不允许有重复的组合。采用通用的思想，时间复杂度为 O(n²)，每次遍历，都跳过已经遍历过得元素，从而避免重复。

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
public static List<List<Integer>> threeSum(int[] nums) {
    int len = nums.length;
    quickSort(nums, 0, len - 1);

    List<List<Integer>> list = new ArrayList<>();
    if (len < 3) return list;
    for (int i = 0; i < len - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        int start = i + 1, end = len - 1;
        while (start < end) {
            int sum = nums[i] + nums[end] + nums[start];
            if (sum > 0) {
                end--;
            } else if (sum < 0) {
                start++;
            } else {
                List<Integer> zero = new ArrayList<>();
                zero.add(nums[i]);
                zero.add(nums[start]);
                zero.add(nums[end]);
                list.add(zero);
                start++;
                end--;
                while (start < end && nums[start] == nums[start - 1]) {
                    start++;
                }
                while (start < end && nums[end] == nums[end + 1]) {
                    end--;
                }
            }
        }
    }
    return list;
}

四数之和（4Sum）

在三数之和的基础上，在外面又包了一层遍历，其时间复杂度为 O(n³)。

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
public static List<List<Integer>> fourSum(int[] nums, int target) {
        int len = nums.length;
        mergeSort(nums, 0, len - 1, new int[len]);
        List<List<Integer>> list = new ArrayList<>();
        if (len < 4) return list;
        for (int i = 0; i < len - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < len - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int m = j + 1, n = len - 1;
                while (m < n) {
                    int sum = nums[i] + nums[j] + nums[m] + nums[n];
                    if (sum < target) {
                        m++;
                    } else if (sum > target) {
                        n--;
                    } else {
                        List<Integer> l = new ArrayList<>();
                        l.add(nums[i]);
                        l.add(nums[j]);
                        l.add(nums[m]);
                        l.add(nums[n]);
                        list.add(l);
                        m++;
                        n--;
                        while (m < n && nums[m] == nums[m - 1]) {
                            m++;
                        }
                        while (m < n && nums[n] == nums[n + 1]) {
                            n--;
                        }
                    }
                }
            }
        }
        return list;
    }

看到这，你就会发现，都是一个模子，思想都是一样的，没错，这也加强了我们的一个意识，如果遇到五个数，六个数，那么都可以采用这个思想来解决问题。