18. 4Sum

题目描述：

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

题目翻译

一个包含n个整数的数组S，判断S中是否存在元素 a + b + c + d = target，查找数组中所有和为 target 的四元组。

注意： 解决方案集不能包含重复的四元组。

例如，数组 S = [1, 0, -1, 0, -2, 2], target = 0.

答案是：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解题方案

标签： Array

思路：

• K sum 是一系列问题，系列问题的解法首先是从 2 sum 开始解决的
• 2 sum 的解决是先对数组进行排序（升序），之后设置begin和end下标，从两侧向中间遍历，sum = nums[begin] + nums[end]
  • if sum == target，则将该组数据加入
  • if sum < target，则左侧数过小，begin++
  • if sum > target，则右侧数过大，end--
  • 遍历结束，获取到所有的二元组
• 3 sum 则是在 2 sum 基础上增加一层遍历，先确定一个元素值first，然后计算 2 sum ，使得 target = first + nums[begin] + nums[end]
• 4 sum 则是在 3 sum 基础上增加一层遍历，先确定一个元素值first，然后计算 3 sum ，再确定一个值second，使得 target = first + second + nums[begin] + nums[end]
• 经过三层遍历，最后时间复杂度为O(n^3)

代码：

class Solution {
    private List<List<Integer>> res = new ArrayList();
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if(nums.length<4)
            return res;
        Arrays.sort(nums);
        for(int i=0;i<nums.length-3;i++){
            if(i>0 && nums[i]==nums[i-1])
                continue;
            threeSum(nums, i+1, nums[i],target);
        }
        return res;
    }

    void threeSum(int[] nums, int loc, int first, int target){
        for(int i=loc;i<nums.length-2;i++){
            if(i>loc && nums[i]==nums[i-1])
                continue;
            twoSum(nums, i+1, nums.length-1, first, nums[i], target);
        }
    }

    void twoSum(int[] nums, int begin, int end, int first, int second, int target){
        while(begin < end){
            if(first + second + nums[begin] + nums[end] == target){
                List<Integer> list = new ArrayList();
                list.add(first);
                list.add(second);
                list.add(nums[begin]);
                list.add(nums[end]);
                res.add(list);
                while(begin < end && nums[begin] == nums[begin+1])
                    begin++;
                while(begin < end && nums[end] == nums[end-1])
                    end--;
                begin++;
                end--;
            }
            else if(first + second + nums[begin] + nums[end] < target)
                begin++;
            else
                end--;
        }
    }
}

参考资料

http://blog.csdn.net/lisonglisonglisong/article/details/45869379