LeetCode-4Sum

4Sum

##题目

####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:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
  • 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)

##解题思路
该题是求解是否存在四个数的和为给定的目标值，根据博客前篇的3Sum和2Sum问题，该题可以将其转化为3Sum,然后再将3Sum变为2Sum问题。而2Sum问题可以通过排序后左右夹逼的方法求解，这里需要注意一点是：重复的元素需要跳过，否则会产生重复的结果。

##算法代码
代码采用JAVA实现：

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class Solution {
	//与求3Sum时利用2sum非常相似，4sum可以利用3sum和2sum求解
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> lists=new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        if(num.length<=3) return lists;
        int len=num.length;
        for(int i=0;i<len-3;i++)
        {
        	if(i>0&&num[i]==num[i-1]) //表示第一个数不会重复
        		continue;
        	threeSum(lists,num,i+1,num[i],target-num[i]);
        }
        return lists;
    }

    public void threeSum(ArrayList<ArrayList<Integer>> lists,int[] num,int start,int term,int target)
    {
    	int len=num.length;
    	for(int i=start;i<len-2;i++)
    	{
    		if(i>start&&num[i]==num[i-1])//表示第二个数不会重复
    			continue;
    		twoSum(lists,num,i+1,term,num[i],target-num[i]);
    	}
    }

    public void twoSum(ArrayList<ArrayList<Integer>> lists,int[] num,int start,int term1,int term2,int target)
    {
    	 int i=start;
    	 int j=num.length-1;
    	 while(i<j)
    	 {
    	 	if((num[i]+num[j])==target)
    	 	{
    	 		ArrayList<Integer> list=new ArrayList<Integer>();
    	 		list.add(term1);
    	 		list.add(term2);
    	 		list.add(num[i]);
    	 		list.add(num[j]);
    	 		lists.add(list);
    	 		i++;
    	 		j--;
    	 		while(i<j&&num[i]==num[i-1]) //表示第三和第四个数不会重复
    	 			i++;
    	 		while(i<j&&num[j]==num[j+1])
    	 			j--;
    	 	}else if((num[i]+num[j])>target)
    	 	{
    	 		j--;
    	 	}else
    	 		i++;
    	 }
    }
}

Comments

▲