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:
這次作業(yè)像捶，還是沒能自己做出來∽椋看了提示拓春，說是用雙指針。我也猜到亚隅。
于是第一步做對(duì)了硼莽，先排個(gè)序。
然后我錯(cuò)誤得將該數(shù)組分成兩類枢步， < 0 為一類沉删， >= 0 為一類。
然后設(shè)置了兩個(gè)指針 head, tail分別指向這個(gè)數(shù)組的頭和尾醉途，想通過這樣的雙指針來解決問題矾瑰。
同時(shí)，我參考了2Sum的解法隘擎，先將head and tail 所指的數(shù)的和的相反數(shù)求出來殴穴，存入哈希表中。然后如果小于0货葬，那就移動(dòng)head指針來找采幌。如果大于0，那就移動(dòng)tail指針來找震桶。
但是問題來了休傍，當(dāng)?shù)扔?時(shí)，如果找到了（nums[middle] == 0 is true）,那么接下來蹲姐， 可能性就會(huì)有三種了磨取，要么head++; 要么 tail--. 要么也可以同時(shí)加減人柿。我的一個(gè)簡(jiǎn)單的循環(huán)，類似于一個(gè)狀態(tài)機(jī)忙厌，無(wú)法在一個(gè)時(shí)刻凫岖，在無(wú)先決條件的情況下，描述出這三種發(fā)展可能性逢净。所以我的程序是錯(cuò)誤的哥放，或者說，我的模型爹土，再次錯(cuò)誤了甥雕。同時(shí)，我還把那個(gè)相反數(shù)存入了哈希表胀茵。下次新的相反數(shù)出現(xiàn)時(shí)犀农，如果哈希表中已經(jīng)存在了，那么就直接跳過宰掉。以此來篩選掉那些重復(fù)情況。這樣其實(shí)也是錯(cuò)的赁濒。
比如 4 + -3 = 1; 哈希表中存放 -1. 3 + -2 = 1轨奄； 此時(shí)完全是另外一種情況，但1已經(jīng)存在于哈希表中了拒炎，于是直接跳過挪拟。造成錯(cuò)誤。
然后這個(gè)時(shí)候我就放棄了击你。上網(wǎng)看了下思路玉组。
發(fā)現(xiàn)該用這種解法。我也不知道為什么自己想不出這種解法丁侄。一個(gè)很大的可能是惯雳。昨天的水桶題也是雙指針，雙指針是從頭和尾巴向中間走鸿摇。于是我就直接把那個(gè)模型套過來了石景。
而這道題目，雖然也是頭指針和尾指針向著中間靠拙吉，但準(zhǔn)確的說潮孽，是有三個(gè)指針的。是不一樣的模型筷黔。
累死了往史。
**
總結(jié)：所以說，雙指針目前碰到的幾個(gè)類型佛舱。
1.徹底的頭指針椎例，尾指針挨决。 水桶題。
2.一個(gè)基指針粟矿，然后跟著頭指針和尾指針凰棉，此道題目就是如此。
3.也有頭指針再加中間一個(gè)指針陌粹，同時(shí)開始跑撒犀。具體題型忘了。
然后掏秩，
List<List<Integer>> result = new List<List<Integer>>(); 是錯(cuò)的或舞。
List<List<Integer>> result = new ArrayList<List<Integer>>(); 是對(duì)的。
因?yàn)?List是一個(gè)接口蒙幻，不能被new映凳。所以只能用ArrayList來代替。
只有類才能new 接口是不能new的邮破。
那么诈豌，接口和抽象類有什么區(qū)別。
抽象類可以實(shí)現(xiàn)方法抒和。接口不行矫渔。
抽象類可以有 static final, 接口不行。
一個(gè)子類只能繼承一個(gè)抽象類摧莽，但可以實(shí)現(xiàn)多個(gè)接口庙洼。
差不多就總結(jié)這些吧。媽的每次凌晨做的題目都好帶勁镊辕！可惜精神狀態(tài)都不是最佳油够。
**
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));
}
}
我自己寫了三種做法，但是沒有一個(gè)通過測(cè)試征懈。
做法一是一個(gè)通解石咬，對(duì) kSum 都可以求解。但是沒有排序卖哎，復(fù)雜度為 O(n ^ 3) 并且常數(shù)系數(shù)比較大碌补。
做法二是對(duì)做法一的優(yōu)化。先排序棉饶，之后當(dāng)發(fā)現(xiàn)和已經(jīng)大于了要求時(shí)表示再也找不到了厦章，就立刻停止。復(fù)雜度仍然為O(n ^ 3),但是常數(shù)系數(shù)會(huì)小一些照藻。
做法三是利用2Sum的模型袜啃。先固定住一個(gè)值，那么后面就是2Sum幸缕，target = -nums[i]
然后復(fù)雜度是O(n ^ 2) 群发，因?yàn)?Sum是O(n). 但是涉及到哈希表的許多操作晰韵，所以常數(shù)系數(shù)不會(huì)小。
然后我看了能通過測(cè)試的做法熟妓，即做法4.
http://www.programcreek.com/2012/12/leetcode-3sum/
復(fù)雜度也是O(n ^ 2), 但是沒有任何哈希操作雪猪，所以常數(shù)系數(shù)小，可以通過測(cè)試起愈。
也是固定住一個(gè)值只恨， target = (-1) * nums[i]. 然后從頭尾同時(shí)開始搜索這個(gè)target，一旦發(fā)現(xiàn)抬虽，加入list官觅。然后呢谅畅，為了避免重復(fù)宋光，start和end需要向左和向右滑行一段记盒，保證下一對(duì)正確的值不再重復(fù)晴及。
同時(shí)，在最外層for循環(huán)中已艰，為了避免重復(fù)祟滴，每次需要判斷當(dāng)前nums[i] 是否和
nums[i - 1] 相等刊懈。如果相等手幢，那么之后找出來的解很有可能是重復(fù)的疑故。所以要避免這種情況。
感覺這道題木還是很經(jīng)典的弯菊。
我一開始直接用DFS的思路來求解，寫起來是簡(jiǎn)單踱阿，但是復(fù)雜度較高管钳。
后來想用2sum來降低復(fù)雜度，但是還是存在大量的哈希操作软舌。
最后才漆，用雙指針，頭尾跑佛点，解決了問題醇滥。
雙指針，頭尾跑超营，經(jīng)常應(yīng)用于已經(jīng)排好序的數(shù)組中鸳玩。
留意。
Anyway, Good luck, Richardo!
