LeetCode三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/3s…

暴力解题 效率很差

public static List<List<Integer>> threeSum(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>> list = new ArrayList<>();
		Set<List<Integer>> set = new HashSet<>();
		for (int i = 0; i < nums.length; i++) {
			for (int j = i+1; j < nums.length; j++) {
				for (int x = j+1; x < nums.length; x++) {
					if(nums[i] + nums[j] + nums[x] == 0) {
						List<Integer> list1 = new ArrayList<>();
						list1.add(nums[i]);
						list1.add(nums[j]);
						list1.add(nums[x]);
						list.add(list1);
						break;
					}
				}
			}
		}
		for(int i = 0; i < list.size(); i++) {
			set.add(list.get(i));
		}
		List<List<Integer>> list2 = new ArrayList<>();
		for (List<Integer> s : set) {
			list2.add(s);
		}
		return list2;
	}

双指针解题思路

例如 int[] nums = {-1, 0, 1, 2, -1, -4};

1. 将数组排序，有小到大。创建返回的结果集。遍历数组。nums = {-4, -1, -1, 0, 1, 2};
2. 判断nums[i]如果等于nums[i-1],就重复了就跳过。
3. 左指针在开始的后一个
4. 右指针在数组的最后
5. 判断左指针小于右指针，计算3数之和
6. 判断是否为0，为0加入结果集
7. 判断左指针下一个数是不是相同的，是就指针加一，跳过=去重
8. 判断右指针下一个数是不是相同的，是就指针加一，跳过=去重
9. 都不是左右指针同时移动
10. 三数之和小于0，说明负数的多，左指针移动
11. 三数之和大于0，说明正数的多，右指针移动
12. 最后返回数据集

public static List<List<Integer>> threeSum(int[] nums) {
		// 1
		Arrays.sort(nums);
		List<List<Integer>> list = new ArrayList<>();
		for (int i = 0; i <nums.length; i++) {
			// 2
			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}
			// 3
			int left = i + 1;
			// 4
			int rigth = nums.length - 1;
			// 5
			while (left < rigth) {
				int sum = nums[i] + nums[left] + nums[rigth];
				// 6
				if (sum == 0) {
					list.add(Arrays.asList(nums[i], nums[left], nums[rigth]));
					// 7
					while(left<rigth && nums[left] == nums[left+1]){left++;}
					// 8
					while(left<rigth && nums[rigth] == nums[rigth-1]){rigth--;}
					//9
					left++;
					rigth--;
				//10
				} else if (sum < 0) {
					left++;
				//11
				} else if (sum > 0) {
					rigth--;
				}
			}
		}
		return list;
	}