4sum

这道题就是在3sum的模板上再套一层循环而已，查重机制也是一模一样的，下面是代码，时间下界就是O(n^3)了

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        n = len(nums)
        A = 0                        # 大写代表坐标，小写代表对应值
        nums.sort()
        res = []

        while A <= n - 4:
            a = nums[A]
            if A > 0 and nums[A] == nums[A - 1]:
                A += 1
                continue
            B = A + 1
            while B <= n - 3:
                b = nums[B]
                if B > A + 1 and nums[B] == nums[B - 1]:
                    B += 1
                    continue
                C, D = B + 1, n - 1
                while C <= D - 1:
                    c, d = nums[C], nums[D]
                    if a + b + c + d == target:
                        res.append([a, b, c, d])
                        while D > C and nums[D] == nums[D - 1]:
                            D -= 1
                        while D > C and nums[C] == nums[C + 1]:
                            C += 1
                        D -= 1
                    elif a + b + c + d < target:
                        C += 1
                    else:
                        D -= 1
                B += 1
            A += 1

        return res

Java版本，注意如何初始化一个arrayList的

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int ori = 0;
        int n = nums.length;

        while (ori <= n - 4) {
            int a = nums[ori];
            if (ori > 0 && nums[ori] == nums[ori - 1]) {
                ori++;
                continue;
            }
            int base = ori + 1;
            while (base <= n - 3) {
                int b = nums[base];
                if (base > ori + 1 && nums[base] == nums[base - 1]) {
                    base++;
                    continue;
                }
                int start = base + 1;
                int end = n - 1;
                while (start <= end - 1) {
                    int c = nums[start];
                    int d = nums[end];
                    if (a + b + c + d == target) {
                        result.add(new ArrayList<>(Arrays.asList(a, b, c, d)));
                        while (start < end && nums[start] == nums[start + 1]) {
                            start++;
                        }
                        while (start < end && nums[end] == nums[end - 1]) {
                            end--;
                        }
                        end--;
                    } else if (a + b + c + d < target) {
                        start++;
                    } else {
                        end--;
                    }
                }
                base++;
            }
            ori++;
        }
        return result;
    }
}