java算法题解Leetcode15三数之和实例

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
	
	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++) {
			// 需要和上一次枚举的数不相同
			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}
			for (int j = i + 1; j < nums.length; j++) {
				// 需要和上一次枚举的数不相同
				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 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
				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;
	}
}