【leetcode系列】3Sum

这个题我最开始的思路是：先一个数定下来，然后在除这个数之外的集合里面找另外两个数，最后计算和。如此反复，对于N个数，需要进行N-2次循环。

我遇到的问题就是怎么找另外两个数，其实我想过参照Two Sum里面的解法，就是用Hashtable存，键值对的结构是<任意两个数的和，<下标1，下标2>>，但是构造这个Hashtable就需要O(N^2)，后面真正解的时候有需要O(N^2)。

参考了大牛的解法后，明白了找两个数还是用两个下标同时往中间移动比较好，下面上代码。

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

public class Solution {
	public static ArrayList<ArrayList<Integer>> threeSum(int[] numbers) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if (numbers.length < 3) {
			return result;
		}
		Arrays.sort(numbers);
		for (int i : numbers) {
			System.out.print(i + " ");
		}
		System.out.println();
		for (int i = 0; i < numbers.length - 2; i++) {
			int lp = i + 1;
			int rp = numbers.length - 1;
			while (lp < rp) {
				int sum = numbers[i] + numbers[lp] + numbers[rp];
				if (sum == 0) {
					ArrayList<Integer> tmp = new ArrayList<Integer>();
					tmp.add(numbers[i]);
					tmp.add(numbers[lp]);
					tmp.add(numbers[rp]);
					result.add(tmp);
					do {
						lp++;
					} while (lp < rp && numbers[lp] == numbers[lp + 1]);
					do {
						rp--;
					} while (lp < rp && numbers[rp] == numbers[rp - 1]);
				} else if (sum < 0) {
					lp++;
				} else if (sum > 0) {
					rp--;
				}
			}
		}
		return result;
	}

	public static void main(String[] args) {
		int[] a = { -1, 0, 1, 2, -1, -4 };
		ArrayList<ArrayList<Integer>> result = threeSum(a);
		for (ArrayList<Integer> item : result) {
			for (Integer i : item) {
				System.out.print(i + " ");
			}
			System.out.println();
		}
	}
}

【leetcode系列】3Sum,布布扣,bubuko.com

【leetcode系列】3Sum

原文：http://blog.csdn.net/a2bgeek/article/details/38414175