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

results matching ""

    No results matching ""