15. 3Sum.md

15. 3Sum

Problem

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)

tag:

• two pointers
• sort

Solution

固定一个数，然后采用two sum方法求解， 注意去除重复元素。

	public List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		Arrays.sort(nums);
		for (int i = 0; i < nums.length; i++) {
			//skip duplicate elements
			if (i - 1 >= 0 && nums[i] == nums[i - 1])
				continue;
			int p1 = i + 1, p2 = nums.length - 1;
			while (p1 < p2) {
				if (nums[p1] + nums[p2] == 0 - nums[i]) {
					res.add(Arrays.asList(nums[i], nums[p1], nums[p2]));
					//skip duplicate elements
					while (p1 + 1 < p2 && nums[p1] == nums[p1 + 1])
						p1++;
					while (p2 - 1 > p1 && nums[p2] == nums[p2 - 1])
						p2--;
					p1++;
					p2--;
				} else if (nums[p1] + nums[p2] < 0 - nums[i])
					p1++;
				else
					p2--;
			}
		}
		return res;
	}

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	var res [][]int = make([][]int, 0, 100)
	for i := 0; i < len(nums); i++ {
		if i >= 1 && nums[i] == nums[i-1] {
			continue
		}
		for p, q := i+1, len(nums)-1; p < q; {
			if nums[p]+nums[q]+nums[i] == 0 {
				res = append(res, []int{nums[i], nums[p], nums[q]})
				for p+1 < q && nums[p+1] == nums[p] {
					p++
				}
				for q-1 > p && nums[q-1] == nums[q] {
					q--
				}
				p++
				q--
			} else if nums[p]+nums[q]+nums[i] < 0 {
				p++
			} else {
				q--
			}
		}
	}
	return res
}