乘风破浪：LeetCode真题_018_4Sum

乘风破浪：LeetCode真题_018_4Sum

一、前言

前面我们已经练习过了三个数相加的集合运算，现在变成了四个数，其实道理是一样的。三个数的时候可以转成两个数的加法，最后来解决，而四个数的可以转换成三个数的加法，最终变成两个数的加法运算。

二、4Sum

2.1 问题

2.2 分析与解决

    根据我们之前的经验，可以很自然地想到变成三个数相加来计算，不过因为是四个数相加，因此需要至少3个循环了，这样时间复杂度就是O(n~3)。下面是这种解法。

class Solution {

    public List<List<Integer>> fourSum(int[] nums, int target) {

        List<List<Integer>> ans = new ArrayList<>();

        if (nums.length == 0) return ans;

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 3; i++) {

            if (i > 0 && nums[i] == nums[i - 1]) continue;

            for (int j = i + 1; j < nums.length - 2; j++) {

                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int k = j + 1, l = nums.length - 1;

                while (k < l) {

                    int sum = nums[i] + nums[j] + nums[k] + nums[l];

                    if (sum < target) k++;

                    else if (sum > target) l--;

                    else {

                        List<Integer> list = new ArrayList<>();

                        list.add(nums[i]);

                        list.add(nums[j]);

                        list.add(nums[k]);

                        list.add(nums[l]);

                        ans.add(list);

                        if (nums[k] == nums[l]) break;

                        while (k + 1 < l && nums[k] == nums[k + 1]) k++;

                        while (l - 1 > k && nums[l] == nums[l - 1]) l--;

                        k++;

                        l--;

                    }

                }

            }

        }

        return ans;

    }

}

    另外我们也可以做一些细节上面优化，这里不再赘述。

三、总结

对于一些类型题，我们只要理解了一些本质，并且在做题的时候多联想一些之前的道理，就能轻松地做出来了。万事开头难，思路是非常重要的。