15.三数之和
想了两个方法。第一个超时，第二个侥幸过关但是用时和内存都消耗过多，以后再来改进。
思路：
- 输入数组长度小于3时肯定返回空List
- 三数相加为0会有如下几种情况：
2.1 三个0
2.2 两负一正（两负相同/两负不同）
2.3 一负一正加个零
2.4 一负两正（两正相同/两正不同）
总共6个点 - 根据以上6个点进行设计，得出List
- 去重：
思路1：得出list后判断是否在结果的list中有出现过
思路2：在遍历时根据从小到大进行过滤 - 排序
题目并没有这样的要求，但是如果提交时集合内不是按照升序会判错。
思路1：在一开始就进行输入的升序排列。遍历时升序遍历找出合适的List加入结果集合。最终的顺序就是升序。
思路2：使用键值对时，在完成集合之后重写sort中的comparator。
/*执行用时：190 ms, 在所有 Java 提交中击败了10.89%的用户
内存消耗：44.1 MB, 在所有 Java 提交中击败了5.00%的用户*/
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ll = new ArrayList<>();
Map<Integer, Integer> negaMap= new HashMap<>();
Map<Integer, Integer> posiMap= new HashMap<>();
int zero = 0;
int len = nums.length;
if(len < 3) return ll;
for(int i = 0; i < len; i++){
if(nums[i] < 0) {
if(!negaMap.containsKey(nums[i])){
negaMap.put(nums[i],1);
}else{
negaMap.put(nums[i], negaMap.get(nums[i]) + 1);
}
}
if(nums[i] == 0) zero++;
if(nums[i] > 0) {
if(!posiMap.containsKey(nums[i])){
posiMap.put(nums[i],1);
}else{
posiMap.put(nums[i], posiMap.get(nums[i]) + 1);
}
}
}
//3个0
if(zero >= 3){
List<Integer> l = new ArrayList<>();
l.add(0);
l.add(0);
l.add(0);
ll.add(l);
}
if(negaMap.isEmpty() || posiMap.isEmpty()) return ll;
for (Map.Entry<Integer, Integer> entry : negaMap.entrySet()){
//2（相同）负数1正数
if(entry.getValue() >= 2 && posiMap.containsKey(entry.getKey() * (-2))){
List<Integer> l = new ArrayList<>();
l.add(entry.getKey());
l.add(entry.getKey());
l.add(entry.getKey() * -2);
ll.add(l);
}
if(posiMap.containsKey(entry.getKey() * (-1)) && zero > 0){
//一正一负一零
List<Integer> l = new ArrayList<>();
l.add(entry.getKey());
l.add(0);
l.add(entry.getKey() * (-1));
ll.add(l);
}
for(Map.Entry<Integer, Integer> entry1 : negaMap.entrySet()){
//2不同负数，1正数
if(entry1.getKey() <= entry.getKey()) continue;
if(posiMap.containsKey((entry1.getKey() + entry.getKey()) * (-1))){
List<Integer> l = new ArrayList<>();
l.add(entry.getKey());
l.add(entry1.getKey());
l.add((entry1.getKey() + entry.getKey()) * (-1));
ll.add(l);
}
}
}
for (Map.Entry<Integer, Integer> entry : posiMap.entrySet()){
//2相同正1负
if(entry.getValue() >= 2 && negaMap.containsKey(entry.getKey() * (-2))){
List<Integer> l = new ArrayList<>();
l.add(entry.getKey() * (-2));
l.add(entry.getKey());
l.add(entry.getKey());
ll.add(l);
}
for(Map.Entry<Integer, Integer> entry1 :posiMap.entrySet()){
if(entry1.getKey() <= entry.getKey()) continue;
//2不同正1负
if(negaMap.containsKey((entry1.getKey() + entry.getKey()) * (-1))){
List<Integer> l = new ArrayList<>();
l.add((entry1.getKey() + entry.getKey()) * (-1));
l.add(entry.getKey());
l.add(entry1.getKey());
ll.add(l);
}
}
}
Collections.sort(ll, new Comparator<List<Integer>>(){
public int compare(List<Integer> l1, List<Integer> l2){
for(int i = 0; i < l1.size(); i++){
if(l1.get(i) > l2.get(i)) return 1;
else if(l1.get(i) < l2.get(i)) return -1;
else continue;
}
return 0;
}
});
return ll;
}
}
//超时
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ll = new ArrayList<>();
//负数集合和整数集合
List<Integer> negalist = new ArrayList<>();
List<Integer> posilist = new ArrayList<>();
//排序，最后不需要再进行排序
Arrays.sort(nums);
int negative_right=-1, positive_left=-1;
//2负1正，2正一负，一正一负一0，三个0
for(int i = 0; i < len-1; i++){
if(nums[i] == 0){
nums0++;
}
if(nums[i] < 0 && nums[i+1]==0){
negative_right = i;
}else if(nums[i] == 0 && nums[i+1] >0){
positive_left = i+1;
}else if(nums[i] < 0 && nums[i+1] > 0){
negative_right = i;
positive_left = i+1;
}
}
if(nums[len-1] == 0) nums0++;
//3个0
if(nums0 >= 3){
List<Integer> l = new ArrayList<>();
l.add(0);
l.add(0);
l.add(0);
ll.add(l);
}
if(negative_right == -1 || positive_left == -1) return ll;
for(int i = 0; i <= negative_right; i++){
//i标在正,k标在负,j标正0负都有
for(int j=len-1; j >= positive_left; j--){
for(int k= i + 1; k < j; k++){
if(nums[i] + nums[j] + nums[k] == 0){
List<Integer> l = new ArrayList<>();
l.add(nums[i]);
l.add(nums[k]);
l.add(nums[j]);
if(!ListContains(l, ll)){
ll.add(l);
}
break;
}
}
}
}
return ll;
}
public boolean ListContains(List<Integer> l1, List<List<Integer>> l2){
//判断结果集合中是否有List，去重
for(List<Integer> l : l2){
if(ListEqual(l, l1)) return true;
}
return false;
}
public boolean ListEqual(List<Integer> l1, List<Integer> l2){
//判断两个List是否相等
if(l1.size() != l2.size()){
return false;
}
for(int i=0; i < l1.size(); i++){
if(l1.get(i) != l2.get(i)){
return false;
}
}
return true;
}
}
