[leetcode] 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)

https://oj.leetcode.com/problems/4sum/

思路：转换成2Sum，注意跟3Sum一样先排序去重。

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
	public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if (num == null || num.length < 4)
			return result;

		int n = num.length;
		Arrays.sort(num);
		int i, j, start, end, sum;
		for (i = 0; i < n - 3; i++) {
			for (j = i + 1; j < n - 2; j++) {
				start = j + 1;
				end = n - 1;
				while (start < end) {
					sum = num[start] + num[end];
					if (sum < target - num[i] - num[j])
						start++;
					else if (sum > target - num[i] - num[j])
						end--;
					else {
						ArrayList<Integer> tmp = new ArrayList<Integer>();
						tmp.add(num[i]);
						tmp.add(num[j]);
						tmp.add(num[start]);
						tmp.add(num[end]);
						result.add(tmp);
						start++;
						end--;
						while (start < j && num[start - 1] == num[start])
							start++;
						while (end >= j + 1 && num[end + 1] == num[end])
							end--;

					}
				}
				while (j < n - 1 && num[j] == num[j + 1])
					j++;
			}
			while (i < n - 1 && num[i] == num[i + 1])
				i++;

		}
		return result;
	}

	public static void main(String[] args) {
		System.out.println(new Solution().fourSum(new int[] { 1, 0, -1, 0, -2,
				2 }, 0));

	}
}

[leetcode] 4Sum,布布扣,bubuko.com

[leetcode] 4Sum

原文：http://www.cnblogs.com/jdflyfly/p/3810696.html