Question:
My code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null)
return null;
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums.length < 3 || nums[0] > 0 || nums[0] + nums[1] + nums[2] > 0)
return result;
for (int i = 0; i < nums.length - 2; i++) {
int negate = -nums[i];
int start = i + 1;
int end = nums.length - 1;
while ((i == 0 || nums[i] != nums[i - 1]) && start < end) {
if (nums[start] + nums[end] > negate) {
end--;
}
else if (nums[start] + nums[end] < negate) {
start++;
}
else {
List<Integer> s = new ArrayList<Integer>();
s.add(nums[i]);
s.add(nums[start]);
s.add(nums[end]);
result.add(s);
start++;
end--;
while (start < end && nums[start] == nums[start - 1])
start++;
while (start < end && nums[end] == nums[end + 1])
end--;
}
}
}
return result;
}
public static void main(String[] args) {
Solution test = new Solution();
int[] a = {-1, 0, 1, 2, -1, -4};
System.out.println(test.threeSum(a));
}
}
My test result:
这次作业，还是没能自己做出来。看了提示，说是用双指针。我也猜到。
于是第一步做对了，先排个序。
然后我错误得将该数组分成两类， < 0 为一类， >= 0 为一类。
然后设置了两个指针 head, tail分别指向这个数组的头和尾，想通过这样的双指针来解决问题。
同时，我参考了2Sum的解法，先将head and tail 所指的数的和的相反数求出来，存入哈希表中。然后如果小于0，那就移动head指针来找。如果大于0，那就移动tail指针来找。
但是问题来了，当等于0时，如果找到了（nums[middle] == 0 is true）,那么接下来， 可能性就会有三种了，要么head++; 要么 tail--. 要么也可以同时加减。我的一个简单的循环，类似于一个状态机，无法在一个时刻，在无先决条件的情况下，描述出这三种发展可能性。所以我的程序是错误的，或者说，我的模型，再次错误了。同时，我还把那个相反数存入了哈希表。下次新的相反数出现时，如果哈希表中已经存在了，那么就直接跳过。以此来筛选掉那些重复情况。这样其实也是错的。
比如 4 + -3 = 1; 哈希表中存放 -1. 3 + -2 = 1； 此时完全是另外一种情况，但1已经存在于哈希表中了，于是直接跳过。造成错误。
然后这个时候我就放弃了。上网看了下思路。
发现该用这种解法。我也不知道为什么自己想不出这种解法。一个很大的可能是。昨天的水桶题也是双指针，双指针是从头和尾巴向中间走。于是我就直接把那个模型套过来了。
而这道题目，虽然也是头指针和尾指针向着中间靠，但准确的说，是有三个指针的。是不一样的模型。
累死了。
**
总结：所以说，双指针目前碰到的几个类型。
1.彻底的头指针，尾指针。 水桶题。
2.一个基指针，然后跟着头指针和尾指针，此道题目就是如此。
3.也有头指针再加中间一个指针，同时开始跑。具体题型忘了。
然后，
List<List<Integer>> result = new List<List<Integer>>(); 是错的。
List<List<Integer>> result = new ArrayList<List<Integer>>(); 是对的。
因为 List是一个接口，不能被new。所以只能用ArrayList来代替。
只有类才能new 接口是不能new的。
那么，接口和抽象类有什么区别。
抽象类可以实现方法。接口不行。
抽象类可以有 static final, 接口不行。
一个子类只能继承一个抽象类，但可以实现多个接口。
差不多就总结这些吧。妈的每次凌晨做的题目都好带劲！可惜精神状态都不是最佳。
**
Anyway, Good luck, Richardo!
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
public class Solution {
/* Solution 1: O(n^k) k = 2, 3, 4, 5, ... general solution
public List<List<Integer>> threeSum(int[] nums) {
ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();
if (nums == null || nums.length <= 2)
return ret;
HashSet<List<Integer>> retSet = new HashSet<List<Integer>>();
ArrayList<Integer> group = new ArrayList<Integer>();
helper(nums, 3, 0, 0, retSet, group);
for (List<Integer> tmp : retSet) {
ret.add(tmp);
}
return ret;
}
private void helper(int[] nums, int k, int begin, int target, HashSet<List<Integer>> retSet, ArrayList<Integer> group) {
if (k == 0) {
int sum = 0;
int[] arr = new int[group.size()];
for (int i = 0; i < group.size(); i++) {
arr[i] = group.get(i);
sum += arr[i];
}
if (sum == target) {
Arrays.sort(arr);
ArrayList<Integer> newGroup = new ArrayList<Integer>();
for (int i = 0; i < arr.length; i++)
newGroup.add(arr[i]);
retSet.add(newGroup);
}
return;
}
for (int i = begin; i < nums.length; i++) {
group.add(nums[i]);
helper(nums, k - 1, i + 1, target, retSet, group);
group.remove(group.size() - 1);
}
}
*/
/* Solution 2: sort to simplify, O(n^k) with a smaller constant
public List<List<Integer>> threeSum(int[] nums) {
ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();
if (nums == null || nums.length <= 2)
return ret;
Arrays.sort(nums);
HashSet<List<Integer>> retSet = new HashSet<List<Integer>>();
ArrayList<Integer> group = new ArrayList<Integer>();
helper(nums, 3, 0, 0, 0, retSet, group);
for (List<Integer> tmp : retSet) {
ret.add(tmp);
}
return ret;
}
private void helper(int[] nums, int k, int begin, int target, int sum, HashSet<List<Integer>> retSet, ArrayList<Integer> group) {
if (k == 0) {
if (sum == target) {
retSet.add(new ArrayList<Integer>(group));
}
return;
}
for (int i = begin; i < nums.length; i++) {
if (sum + nums[i] > target)
break;
group.add(nums[i]);
helper(nums, k - 1, i + 1, target, sum + nums[i], retSet, group);
group.remove(group.size() - 1);
}
}
*/
/* Solution 3: sort, use 2Sum model, O(n^2) with larger constant because of Hash operation
public List<List<Integer>> threeSum(int[] nums) {
ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();
if (nums == null || nums.length <= 2)
return ret;
Arrays.sort(nums);
HashSet<List<Integer>> retSet = new HashSet<List<Integer>>();
for (int i = 0; i < nums.length; i++) {
helper(nums, i, retSet);
}
for (List<Integer> tmp : retSet) {
ret.add(tmp);
}
return ret;
}
private void helper(int[] nums, int targetIndex, HashSet<List<Integer>> retSet) {
HashMap<Integer, Integer> tracker = new HashMap<Integer, Integer>();
int target = (-1) * nums[targetIndex];
for (int i = targetIndex + 1; i < nums.length; i++) {
if (tracker.containsKey(nums[i])) {
ArrayList<Integer> group = new ArrayList<Integer>();
group.add((-1) * target);
group.add(nums[tracker.get(nums[i])]);
group.add(nums[i]);
retSet.add(group);
}
else {
if (target - nums[i] < nums[i])
break;
tracker.put(target - nums[i], i);
}
}
}
*/
/** Solution 4: pass all online tests. O(n ^ 2) with smaller constant */
public List<List<Integer>> threeSum(int[] nums) {
ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();
if (nums == null || nums.length <= 2)
return ret;
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (i >=1 && nums[i] == nums[i - 1])
continue;
int target = (-1) * nums[i];
int start = i + 1;
int end = nums.length - 1;
while (start < end) {
int sum = nums[start] + nums[end];
if (sum < target)
start++;
else if (sum > target)
end--;
else {
ArrayList<Integer> group = new ArrayList<Integer>();
group.add(nums[i]);
group.add(nums[start]);
group.add(nums[end]);
ret.add(group);
start++;
end--;
while (nums[start] == nums[start - 1] && start < end)
start++;
while (nums[end] == nums[end + 1] && start < end)
end--;
}
}
}
return ret;
}
public static void main(String[] args) {
Solution test = new Solution();
int[] nums = new int[] {-1, 0, 1, 2, -1, -4};
System.out.println(test.threeSum(nums));
}
}
我自己写了三种做法，但是没有一个通过测试。
做法一是一个通解，对 kSum 都可以求解。但是没有排序，复杂度为 O(n ^ 3) 并且常数系数比较大。
做法二是对做法一的优化。先排序，之后当发现和已经大于了要求时表示再也找不到了，就立刻停止。复杂度仍然为O(n ^ 3),但是常数系数会小一些。
做法三是利用2Sum的模型。先固定住一个值，那么后面就是2Sum，target = -nums[i]
然后复杂度是O(n ^ 2) ，因为2Sum是O(n). 但是涉及到哈希表的许多操作，所以常数系数不会小。
然后我看了能通过测试的做法，即做法4.
http://www.programcreek.com/2012/12/leetcode-3sum/
复杂度也是O(n ^ 2), 但是没有任何哈希操作，所以常数系数小，可以通过测试。
也是固定住一个值， target = (-1) * nums[i]. 然后从头尾同时开始搜索这个target，一旦发现，加入list。然后呢，为了避免重复，start和end需要向左和向右滑行一段，保证下一对正确的值不再重复。
同时，在最外层for循环中，为了避免重复，每次需要判断当前nums[i] 是否和
nums[i - 1] 相等。如果相等，那么之后找出来的解很有可能是重复的。所以要避免这种情况。
感觉这道题木还是很经典的。
我一开始直接用DFS的思路来求解，写起来是简单，但是复杂度较高。
后来想用2sum来降低复杂度，但是还是存在大量的哈希操作。
最后，用双指针，头尾跑，解决了问题。
双指针，头尾跑，经常应用于已经排好序的数组中。
留意。
Anyway, Good luck, Richardo!
