LeetCode（三）关于ThreeSum的实现

题目：

给定一个整数数组，找出里面所有三个元素之和为0的组合，返回的组合不能有重复，且每一个组合中的三个元素按从小到大排序。

/**
 * Given an array S of n integers, are there elements a, b, c in S such that a +
 * b + c = 0? Find all unique triplets in the array which gives the sum of zero.
 * 
 * Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤
 * b ≤ c) The solution set must not contain duplicate triplets. For example,
 * given array S = {-1 0 1 2 -1 -4},
 * 
 * A solution set is: (-1, 0, 1) (-1, -1, 2)
 * 
 * 
 *

解题思路：

1）将数组排序。

2）对数组中每一个元素，假设其值为 a，则问题可化为在剩余的数组中（除了当前元素）找 target 为 -a 的TwoSum问题。

3）由于数组是有序的，剩余的两个值一个比a小，在a的左边数组中，一个比a大，在a的右边数组中。

4）指定数组中最小的数（即最左边的数）为第一个数 low ，指定数组中最大的数为第二个数 high。

5）比较这两个数的和 sum 跟 target 的大小，如果 sum < target，表明 low 位置的值太小，则 low位置的数要往前移（low++），如果sum > target，则 high 位置的值太大，high往后移（high--），在移动过程，判断是否达到a所在的位置，如果忆经达a所在的位置，还没有找到，则说明，不存在这样的组合。

6）如果存在这样的组合，判断是否存在这样的组合，如果不存在这样的组合，则将其添加进结果列表中，如果存在，则舍弃它。

7）对于同样的值 a ，剩余数组中可能存在不只一对元素的和等于 -a，所以不像TwoSum问题直接退出，要继续向前移动 low 和向后移动 high，找出同样满足条件的数值对。

8）由于数组中有可能存在重复的数，在排序后的数组中，它们是连在一起的，那么当找到第一对数值对的时候，继续找的时候，要判断下一个位置的数是否跟当前位置的置相同，如果相同，可忽略，因为这个值同样满足条件，但是其会造成重复的组合。

代码：

public class ThreeSum {

	public static void main(String[] args) {
		long startTime = System.currentTimeMillis();
		ThreeSum ts = new ThreeSum();
		int[] num = {-7,2,1,10,9,-10,-5,4,13,-9,-4,6,11,-12,-6,-9,-6,-9,-11,-4,10,10,-3,-1,-4,-7,-12,-15,11,5,14,11,-7,-8,6,9,-2,9,-10,-12,-15,2,10,4,5,11,10,6,-13,6,-13,12,-7,-9,-12,4,-9,13,-4,10,4,-12,6,4,-5,-10,-2,0,14,4,4,6,13,-9,-5,-5,-13,12,-14,11,3,10,8,11,-13,4,-8,-7,2,4,10,13,7,2,2,9,-1,8,-5,-10,-3,6,3,-5,12,6,-3,6,3,-2,2,14,-7,-13,10,-13,-2,-12,-4,8,-1,13,6,-9,0,-14,-15,6,9};
//		int[] num = {7,-1,14,-12,-8,7,2,-15,8,8,-8,-14,-4,-5,7,9,11,-4,-15,-6,1,-14,4,3,10,-5,2,1,6,11,2,-2,-5,-7,-6,2,-15,11,-6,8,-4,2,1,-1,4,-6,-15,1,5,-15,10,14,9,-8,-6,4,-6,11,12,-15,7,-1,-9,9,-1,0,-4,-1,-12,-2,14,-9,7,0,-3,-4,1,-2,12,14,-10,0,5,14,-1,14,3,8,10,-8,8,-5,-2,6,-11,12,13,-7,-12,8,6,-13,14,-2,-5,-11,1,3,-6};
//		int[] num = {0,0,0};
		ArrayList<ArrayList<Integer>> list = ts.threeSum(num);
		long endTime = System.currentTimeMillis();
		Helper.println("Time cost : " + (endTime - startTime));
		Helper.println("list.size = " + list.size());
		for(ArrayList<Integer> al : list){
			Helper.printArray(al);
		}
	}

	public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();		
		Arrays.sort(num);
		int len = num.length;
		HashSet<int[]> visited = new HashSet<>();
		for (int i = 1; i < len-1; i++) {			
			findOtherTwo(num, 0 - num[i], i, visited, result);
		}
		return result;
	}

	private boolean existed(HashSet<int[]> set, int[] tmp) {
		for (int[] a : set) {
			if (a[0] == tmp[0] && a[1] == tmp[1] && a[2] == tmp[2]) {
				return true;
			}
		}
		return false;
	}

	public void findOtherTwo(int[] numbers, int target, int k,
			HashSet<int[]> set, ArrayList<ArrayList<Integer>> result) {
		int len = numbers.length;		
		int low = 0;
		int high = len-1;
		while(low < high && low < k && high > k){
			if(numbers[low] + numbers[high] < target){
				low++;
				continue;
			}
			if(numbers[low] + numbers[high] > target){
				high--;
				continue;
			}
			int[] tmp = new int[] { numbers[low], numbers[k], numbers[high] };
			if (!existed(set, tmp)) {
				ArrayList<Integer> al = new ArrayList<Integer>();
				for (int t : tmp) {
					al.add(t);
				}
				result.add(al);
				set.add(tmp);
			}
			while(low < k && numbers[low] == tmp[0]){
				low++;				
			}
			while(high > k && numbers[high] == tmp[2]){
				high--;
			}			
		}	
	}	
}

LeetCode（3）关于ThreeSum的实现

题目：

解题思路：

代码：

相关推荐