15. 三数之和

问题15 三数之和 ★★☆☆☆

https://leetcode-cn.com/problems/3sum/

题目本身很好理解，给定一个数组，找出所有相加之和为0的三元组，注意还需要对三元组去重。

如果从暴力解法入手，直接三重循环，是很容易找出所有满足条件的三元组的，但一方面这种做法时间效率较差，另一方面如何对三元组去重呢？

把这个题目和问题1、问题167放到一起来看，我们可以先排序，排序以后循环处理，每次循环固定一个元素，从剩余元素中按问题167中的双指针解法确定另两个元素。另外，通过判断固定的数是不是已经处理过来去重。这样一个解题思路，如果基于问题1、问题167来思考，倒也不显得很难。但是，如果没有问题1、问题167打底，思路上又有一定难度。

	public List<List<Integer>> threeSum(int[] nums) {
		int len = nums.length;
		if (len == 0) {
			return Collections.emptyList();
		}

		Arrays.sort(nums);

		List<List<Integer>> ret = new ArrayList<>();
		for (int i = 0; i < len; i++) {
			if (i > 0 && nums[i] == nums[i-1]) {
				continue;
			}

			int target = 0 - nums[i];
			int j = i + 1, k = len - 1;
			while (j < k) {
				if (j > i+1 && nums[j] == nums[j-1]) {
					j++;
					continue;
				}

				int curSum = nums[j] + nums[k];
				if (curSum > target) {
					k--;
				} else if (curSum < target) {
					j++;
				} else {
					ret.add(Arrays.asList(nums[i], nums[j], nums[k]));
					j++;
					k--;
				}
			}
		}

		return ret;
	}

在 LeetCode 查看