Question:
My code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
if (nums == null)
return null;
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums.length < 3)
return result;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
if (i == 0 || nums[i] != nums[i - 1])
threeSumClosest(nums, i + 1, target - nums[i], result);
}
return result;
}
private void threeSumClosest(int[] nums, int head, int target, List<List<Integer>> result) {
if (nums == null || nums.length < 3)
return;
HashMap<Integer, Integer> h = new HashMap<Integer, Integer>();
for (int i = head; i < nums.length - 2; i++) {
int findResult = target - nums[i];
//if (h.containsKey(findResult))
//continue;
//else
//h.put(findResult, nums[i]);
int start = i + 1;
int end = nums.length - 1;
while ((i == head || nums[i] != nums[i - 1]) && start < end) {
if (nums[start] + nums[end] > findResult) {
end--;
while (start < end && nums[end] == nums[end + 1])
end--;
}
else if (nums[start] + nums[end] < findResult) {
start++;
while (start < end && nums[start] == nums[start - 1])
start++;
}
else {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[head - 1]);
list.add(nums[i]);
list.add(nums[start]);
list.add(nums[end]);
result.add(list);
start++;
end--;
while (start < end && nums[start] == nums[start - 1])
start++;
while (start < end && nums[end] == nums[end + 1])
end--;
}
}
}
}
public static void main(String[] args) {
Solution test = new Solution();
int[] nums = {-1,-5,-5,-3,2,5,0,4};
System.out.println(test.fourSum(nums, -7));
}
}
My test result:
这次作业基本是一开始就有了思路。那就是用之前3Sum写好的代码来为4Sum服务。
但是3Sum是默认target = 0. 而此题，我是先将第一个数固定住，然后
target = target - nums[i]. 作为target传入子方法中，所以我选择了3Sum Closet.并且稍微改进了下。
因为之前这道题目是默认，只有一个组合是最接近的.但同样他也进行了遍历以获得最接近值。那么我就可以利用这个遍历的过程，找出那些 = target的组合，并且存入List中。
然后我看了下评论，的确我发现我这个算法有个多此一举的地方。
那就是每次我都有一个操作哈希表的过程。这是为了避免重复搜索。
那么，既然我已经保证 nums[i] != nums[i - 1]，那么我就不用担心会发生重复的问题了。之前在3Sums Closest 中我也考虑了这个问题，没有深思，觉得影响不大。结果这道题目在删除这段代码之前，跑的时间是708ms，很慢。如图。
但是， 删除这段代码后，速度就一下子快了，时间是480ms。所以，别看哈希表操作是常数级别操作。如果遍历级别是 o(n ^ 2)， 那么哈希表加起来的总时间也是o(n ^ 2).不可忽视的！
That's it.
那么，咱们来头脑风暴下。能不能用一段类似的代码，解决kSum的问题。
给你，nums[], target, k
答案是一定的。如何做。
用递归。并且每次 k 都减一。直到 k == 3 的时候，就可以直接用源代码了。
伪代码如下。
private kSum(int head, int[] nums, List... result, int k, int target) {
if (k > 3) {
for(int i = head; i < length - k + 1; i++) {
kSum(i + 1, nums, result, k - 1, target - nums[i]);
}
}
else {
// do what we do in 3Sum
}
}
感觉差不多就是类似的代码，然后就可以解决 kSum问题。
**
总结：今天的总结比较重要。
kSum问题就可以这么解决了。
然后问了下同学，怎么解决点到value的映射，并且存入哈希表中，即：
KEY: (int x, int y) ------>>> VALUE: int val
他的方法很实用。写一个方法，
private String getPoint(int x, int y) {
return Integer.toString(x) + ":" + Integer.toString(y);
}
就是说，将 x,y 组成 "x:y" 的字符串作为Key存入哈希表中。提取的时候
x = Integer.parseInt(str.charAt(0));
y = Integer.parseInt(str.charAt(2));
然后这样，就可以解决这个问题了。
对了，单独写方法来提取String和根据String获得两坐标，叫做，封装。
然后说真正的要紧事吧。初中的时候班上有个班花，算是女神级别的。然后我也从来没敢加她QQ。女神吗，我这样的屌丝，肯定不敢和她说话。
然后今天竟然和她偶遇了，在Leetcode 刷题群里。。。
然后我自信多了。主动加了她好友。毕竟背后站着我大康。。。然后聊了聊。
只不过女神也是初中时代的我的心中的女神了。现在。。。只是不感兴趣了。
女朋友做事风格，我还是受不了。不知道最近为什么这么强烈。好多次了。
一开始不准备，然后我一直催，发火。最后关头，新的事又出现了，忙成一团。我再催，再发火。
但她是我的女朋友啊，第一个。以后的路，还是得好好走下去。
不管未来怎么样，先见面再说吧。呵呵，见面。
**
Anyway, Good luck, Richardo!
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 4)
return ret;
Arrays.sort(nums);
ArrayList<Integer> group = new ArrayList<Integer>();
helper(nums, 4, 0, target, ret, group);
return ret;
}
private void helper(int[] nums, int k, int begin, int target, ArrayList<List<Integer>> ret, ArrayList<Integer> group) {
if (k > 2) {
for (int i = begin; i < nums.length; i++) {
if (i > begin && nums[i] == nums[i - 1])
continue;
group.add(nums[i]);
helper(nums, k - 1, i + 1, target - nums[i], ret, group);
group.remove(group.size() - 1);
}
}
else {
int start = begin;
int end = nums.length - 1;
while (start < end) {
int sum = nums[start] + nums[end];
if (sum < target)
start++;
else if (sum > target)
end--;
else {
group.add(nums[start]);
group.add(nums[end]);
ret.add(new ArrayList<Integer>(group));
group.remove(group.size() - 1);
group.remove(group.size() - 1);
start++;
end--;
while (nums[start] == nums[start - 1] && start < end)
start++;
while (nums[end] == nums[end + 1] && start < end)
end--;
}
}
}
}
public static void main(String[] args) {
Solution test = new Solution();
int[] nums = new int[] {0, 0, 0, 0};
System.out.println(test.fourSum(nums, 0));
}
}
这就是一个kSum的通解做法，复杂度为O(n ^ (k - 1)).
其中，LJ中，2Sum比较特殊。他需要返回的是index而不是value，所以用排序来做有点不方便。
上面的总结很好，
**
所以，别看哈希表操作是常数级别操作。如果遍历级别是 o(n ^ 2)， 那么哈希表加起来的总时间也是o(n ^ 2).不可忽视的！
**
Anyway, Good luck, Richardo!
