p15

发表于 | 分类于 |

LeetCode 15 3Sum 题解

1.题目：

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: 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]
]

题意：

输入一个数组，找出所有某3个数加起来和为0的组合。

2.解题思路:

悲伤望天！！！写了好久！！！人肉debug!!最后发现超时！！继续折腾！！折腾了好几种！！又回来。。终于没超时了TUT。
以上是心路历程。。具体与2sum差不多，不过两层循环，left,right向中间查找，注意去重的循环，不加会超时。听说可以二分，第一次尝试失败之后，已躺尸，待填TUT

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 

public class Solution {
   	public List<List<Integer>> threeSum(int[] nums) {

		List<List<Integer>> ans = new ArrayList<>();

		HashSet<List<Integer>> set = new HashSet<>();
		if (nums.length < 3)
			return ans;

		Arrays.sort(nums);
		
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] > 0)
				break;
		
			int k = nums.length - 1;
			for (int j = i + 1; j < k;) {
				if (nums[i] + nums[j] + nums[k] == 0) {
				List<Integer> l = new ArrayList<Integer>();
				l.add(nums[i]);
				l.add(nums[j]);
				l.add(nums[k]);
				if (set.add(l))
					ans.add(l);
				//j++;
				k--;
				while (j-1>0&&j + 1 < nums.length - 1 && nums[j] == nums[j + 1]) {
					j++;
				}//这个循环不加会超时，悲伤望天，剔除重复的
			} else if (nums[i] + nums[j] + nums[k] < 0)
				{
				j++;
				}
			else
				{
				k--;	
				}
				


			}
			while (i + 1 < nums.length - 2 && nums[i] == nums[i + 1]) {
				i++;
			}
		}

		for (List<Integer> s : ans) {
			System.out.println(s.toString());

		}
		return ans;
	}
}

4.一些总结：别急着换方法，注意边界和优化。