[leetcode]3Sum

新博文地址：

[leetcode]3Sum

http://oj.leetcode.com/problems/3sum/

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)

这道题并没有想象中的那么简单.....+_+///最直观的想法肯定是三次遍历，算和，过滤，时间复杂度为O(n^3)压根就不用实现，肯定会超时。再一想：先排序，然后维护两个指针a,b，比如说a从0~ n - 2，b从1~n-1，然后根据二分查找，从b后面的数中找-a-b，时间复杂度为O(n*n*logN)我没实现，我觉得也肯定要TLE，后来手贱google了一下，惊奇的发现，原来rSum这个问题居然是 computational complexity theory中一个经典的问题，真是小看它了，绝逼的扮猪吃虎啊，其时间复杂度最小是O(n^2)

根据维奇百科中的解释，该题的一般解法有两种：

1 . Suppose the input array is S[0..n-1]. 3SUM can be solved in O(n^2) time by inserting each number S[i] into a hash table, and then for each index i and j, checking whether the hash table contains the integer -S[i]-S[j].

2 . Alternatively, the algorithm below first sorts the input array and then tests all possible pairs in a careful order that avoids the need to binary search for the pairs in the sorted list, again achieving O(n^2) time 

第一种解法需要建hash表，我怕空间复杂度过大，就用的第二种，有兴趣的同学可以实现一下第一种方法。

第二种算法维护了三个指针，a,b,c。

-25 -10 -7 -3 2 4 8 10 (a+b+c==-25)
-25 -10 -7 -3 2 4 8 10 (a+b+c==-22)
. . .
-25 -10 -7 -3 2 4 8 10 (a+b+c==-7)
-25 -10 -7 -3 2 4 8 10 (a+b+c==-7)
-25 -10 -7 -3 2 4 8 10 (a+b+c==-3)
-25 -10 -7 -3 2 4 8 10 (a+b+c==2)
-25 -10 -7 -3 2 4 8 10 (a+b+c==0)

 其中a逐个往后遍历，b，c指针从a后面的数中找出满足条件的b和c，具体啥时候移动b啥时候移动c是很容易的。比较麻烦的一点是：如何过滤？

首先来看这组实例：

-4 -3 -2 0 1 2 3 4

首先我们把a指向-4，b指向-3，c指向4，容易发现-4 -3 + 4 < 0，因此希望值增大一点，需要移动b.

找到-4+0+4=0满足条件，这时候应该移动谁呢？答案是b,c皆可。因为需要找到下一个和为4 的两个数，两个指针都必须往中间移动，这里，我们约定，先移动b，再移动c。

如果我们往数组中插入几个数：-4 -3 -2 0 0 0 0 1 2 3 4

我们希望找到一直将b移动到与0不同的数，因此这里为了过滤，需要加一个判断。（标注1）

 

同理，这样插入几个数：-4 -4 -4 -4 -3 -2 0 1 2 3 4

就需要对a的移位进行判断，过滤掉已经处理过的数（标注2）

 

可能说的比较乱。还是看代码吧

public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
		if (num == null || num.length < 3) {
			return new ArrayList<ArrayList<Integer>>();
		}
		int length = num.length;
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		mergeSort(num, 0, length - 1);
		for(int i = 0; i <= length - 3; i++){
			if(i > 0 && num[i] == num[i - 1]){（标注2）
				continue;
			}
			int a = i, b = i + 1,c = length -1;
			while(b < c){
				if(num[a] + num[b] + num[c] == 0){
					ArrayList<Integer> node = new ArrayList<Integer>();
					node.add(num[a]);
					node.add(num[b]);
					node.add(num[c]);
					result.add(node);
					do{（标注1）
						b++;
					}while(num[b] == num[b - 1] && b < c);
				}else if(num[a] + num[b] + num[c] < 0){
					b++;
				}else{
					c--;
				}
			}
		}
		return result;
	}

 

 其中的排序方法采取的是归并排序，代码如下：

	private void mergeSort(int[] sum, int begin, int end) {
		if (sum == null || begin == end) {
			return;
		}
		int mid = (begin + end) / 2;
		mergeSort(sum, begin, mid);
		mergeSort(sum, mid + 1, end);
		merge(sum, begin, mid, end);
	}

	private void merge(int[] sum, int begin, int mid, int end) {
		int[] former = new int[mid - begin + 2];
		int[] latter = new int[end - mid + 1];
		for (int i = begin; i <= end; i++) {
			if (i <= mid) {
				former[i - begin] = sum[i];
				if (i == mid) {
					former[mid - begin + 1] = Integer.MAX_VALUE;
				}
			} else {
				latter[i - mid - 1] = sum[i];
				if (i == end) {
					latter[end - mid] = Integer.MAX_VALUE;
				}
			}
		}
		int index = begin;
		int formerIndex = 0, latterIndex = 0;
		while (index <= end) {
			sum[index++] = former[formerIndex] < latter[latterIndex] ? former[formerIndex++] : latter[latterIndex++];
		}
	}