15.三數(shù)之和
想了兩個方法。第一個超時，第二個僥幸過關但是用時和內存都消耗過多，以后再來改進。
思路：
- 輸入數(shù)組長度小于3時肯定返回空List
- 三數(shù)相加為0會有如下幾種情況：
2.1 三個0
2.2 兩負一正（兩負相同/兩負不同）
2.3 一負一正加個零
2.4 一負兩正（兩正相同/兩正不同）
總共6個點 - 根據以上6個點進行設計，得出List
- 去重：
思路1：得出list后判斷是否在結果的list中有出現(xiàn)過
思路2：在遍歷時根據從小到大進行過濾 - 排序
題目并沒有這樣的要求，但是如果提交時集合內不是按照升序會判錯。
思路1：在一開始就進行輸入的升序排列。遍歷時升序遍歷找出合適的List加入結果集合。最終的順序就是升序。
思路2：使用鍵值對時，在完成集合之后重寫sort中的comparator。
/*執(zhí)行用時：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（相同）負數(shù)1正數(shù)
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不同負數(shù)，1正數(shù)
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<>();
//負數(shù)集合和整數(shù)集合
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;
}
}
