import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
	/**
	 * 解題思路
	 * 暴力解法：如果直接采用三層for循環(huán)，然后去遍歷，找到三個元素，然后通過hashset或者自定義類，來去重，這樣肯定超時
	 * 1.我們需要去想一下，如何優(yōu)化算法，條件是a+b+c==0，其實我們可以優(yōu)化為找到a+b==-c
	 * 2.三層for循環(huán)是根本，第一層和第二層循環(huán)不可避免，第三層需要可以利用a+b==-c的點來優(yōu)化
	 * 3.如何優(yōu)化？我們想到這個是一個整數(shù)數(shù)組，如果我把它排序之后，其實第二層遍歷和第三層遍歷，完全可以使用雙指針方案來優(yōu)化
	 * 4.第三層for循環(huán)，可以優(yōu)化為一個k指針（默認位置為int k = nums.length - 1），有一個k指針從后往前，找尋nums[j] + nums[k]  == nums[i]的元素
	 * 5.如果k--，一直往前找，依然無法找到，則無法找到
	 * 6.如果有滿足的元素，則這時為結(jié)果元素
	 * 7.還剩余一個問題，如何去重?題目中要求我們不能有重復(fù)元素，也是利用數(shù)組已排序的點，如果數(shù)組排序之后，遍歷過程中發(fā)現(xiàn)和前一個元素相同，則實際上就是重復(fù)了
	 * @param nums
	 * @return
	 */
	public List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> target = new ArrayList<List<Integer>>();
		if (nums == null || nums.length < 2) {
			return target;
		}
		Arrays.sort(nums);
		for (int i = 0; i < nums.length; i++) {
			// 需要和上一次枚舉的數(shù)不相同
			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}
			for (int j = i + 1; j < nums.length; j++) {
				// 需要和上一次枚舉的數(shù)不相同
				if (j > i + 1 && nums[j] == nums[j - 1]) {
					continue;
				}
				int temp = -nums[i];
				int k = nums.length - 1;
				while (nums[j] + nums[k] > temp && j < k) {
					k--;
				}
				// 如果指針重合，隨著 b 后續(xù)的增加
                // 就不會有滿足 a+b+c=0 并且 b<c 的 c 了，可以退出循環(huán)
				if (j == k) {
					break;
				}
				if (nums[i] + nums[j] + nums[k] == 0) {
					List<Integer> list = new ArrayList<Integer>();
					list.add(nums[i]);
					list.add(nums[j]);
					list.add(nums[k]);
					target.add(list);
				}
			}
		}
		return target;
	}
}