leetcode:java.T018_4Sum---给定一个整数数组，找出a + b + c + d = target的惟一解,不能有重复元素组

<span style="color:#ff4635">敬请关注博客，后期不断更新优质博文，谢谢</span>

package leetcode.T018_4Sum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Title: Solution.java
 * @Package leetcode.T018_4Sum
 * @Description: TODO
 * @author zhouzhixiang
 * @date 2017-6-8 下午1:19:08
 * @version V1.0
 */
public class Solution {
	/**
	 * <pre>
	 * 原题
	 * 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)
	 * 
	 * 题目大意
	 * 给定一个整数数组，找出a + b + c + d = target的惟一解。
	 * 
	 * 解题思路
	 * 先肯定a和d的两个数，对于a和d两个数，不能同时重复使用。而后再肯定b和c，一样这两个数也不能
	 * 同时重复使用。找出全部知足条件的解，同时能够保证解不重复。
	 * </pre>
	 * 
	 * @param num
	 * @param target
	 * @return
	 */
	public static void main(String[] args) {
		int[] arr = { 1, 0, -1, 0, -2, 2 };
		int target = 0;
		new Solution().fourSum(arr, target);
//		new Solution().find4Sum(arr, target);
	}

	/**
	 * @Title: find4Sum
	 * @Description: zhouzhixiang-First:简便
	 * @param @param arr
	 * @param @param target
	 * @param @return
	 * @return String
	 * @throws
	 */
	public String find4Sum(int[] arr, int target) {

		// 四元素之和
		int sum = 0;

		if (arr.length < 4 || arr == null) {
			return null;
		}

		Arrays.sort(arr);

		// 输出结果
		String result = "";
		for (int a = 0; a < arr.length - 3; a++) {
			for (int b = a + 1; b < arr.length - 2; b++) {
				for (int c = b + 1; c < arr.length - 1; c++) {
					for (int d = c + 1; d < arr.length; d++) {
						sum = arr[a] + arr[b] + arr[c] + arr[d];
						if (sum == target && arr[a] <= arr[b]
								&& arr[b] <= arr[c] && arr[c] < arr[d]) {
							result += "( " + arr[a] + ", " + arr[b] + ", "
									+ arr[c] + " , " + arr[d] + " ),";
						}
					}
				}
			}
		}

		result = result.substring(0, result.length() - 1);

		System.out.println(result);
		return result;
	}

	/**
	* @Title: fourSum 
	* @Description: 参考：比较简便
	* @param @param arr
	* @param @param target
	* @param @return    
	* @return List<List<Integer>>    
	* @throws
	 */
	public List<List<Integer>> fourSum(int[] arr, int target) {

		List<List<Integer>> result = new LinkedList<>();

		if (arr == null || arr.length < 4) {
			return result;
		}

		Arrays.sort(arr);

		// 第一个数
		for (int i = 0; i < arr.length-3; i++) {
			// 第一个数使用不重复
			if (i > 0 && arr[i] == arr[i - 1]) {
				continue;
			}
			
			// 第四个数
			for (int j = arr.length-1; j>i+2; j--) {
				// 第四个数使用不重复
				if(j<arr.length-1 && arr[j]==arr[j+1]){
					continue;
				}
				
				// 第二个数肯能的起始位置
				int start = i+1;
				// 第三个可能的数的结束位置
				int end = j-1;
				int n = target - arr[i] - arr[j];
				
				while(start<end){
					
					if(arr[start] + arr[end]==n){
						List<Integer> four = new ArrayList<>(4);
						four.add(arr[i]);
						four.add(arr[start]);
						four.add(arr[end]);
						four.add(arr[j]);
						
						result.add(four);
						
						do {
							start++;
						} while (start<end && arr[start]==arr[start-1]); // 第二个数保证不重复
						
						do {
							
						} while (start<end && arr[end]==arr[end+1]); // 第三个数保证不重复
						
					}else if(arr[start] + arr[end]>n){
					    do {
							end--;
						} while (start<end && arr[end]==arr[end+1]);
					    
					}else{
						do {
							start++;
						} while (start<end && arr[start]==arr[start-1]);
					}
					
					
				}
			}
		}
                System.out.println(result);
		return result;
	}

}

欢迎加入Java猿社区
 java