15.三數(shù)之和
想了兩個(gè)方法。第一個(gè)超時(shí)，第二個(gè)僥幸過關(guān)但是用時(shí)和內(nèi)存都消耗過多，以后再來改進(jìn)。
思路：
- 輸入數(shù)組長度小于3時(shí)肯定返回空List
- 三數(shù)相加為0會有如下幾種情況：
2.1 三個(gè)0
2.2 兩負(fù)一正（兩負(fù)相同/兩負(fù)不同）
2.3 一負(fù)一正加個(gè)零
2.4 一負(fù)兩正（兩正相同/兩正不同）
總共6個(gè)點(diǎn) - 根據(jù)以上6個(gè)點(diǎn)進(jìn)行設(shè)計(jì)丰捷，得出List
- 去重：
思路1：得出list后判斷是否在結(jié)果的list中有出現(xiàn)過
思路2：在遍歷時(shí)根據(jù)從小到大進(jìn)行過濾 - 排序
題目并沒有這樣的要求，但是如果提交時(shí)集合內(nèi)不是按照升序會判錯(cuò)寂汇。
思路1：在一開始就進(jìn)行輸入的升序排列病往。遍歷時(shí)升序遍歷找出合適的List加入結(jié)果集合。最終的順序就是升序健无。
思路2：使用鍵值對時(shí)荣恐，在完成集合之后重寫sort中的comparator。
/*執(zhí)行用時(shí)：190 ms, 在所有 Java 提交中擊敗了10.89%的用戶
內(nèi)存消耗：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個(gè)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（相同）負(fù)數(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){
//一正一負(fù)一零
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不同負(fù)數(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負(fù)
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負(fù)
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;
}
}
//超時(shí)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ll = new ArrayList<>();
//負(fù)數(shù)集合和整數(shù)集合
List<Integer> negalist = new ArrayList<>();
List<Integer> posilist = new ArrayList<>();
//排序，最后不需要再進(jìn)行排序
Arrays.sort(nums);
int negative_right=-1, positive_left=-1;
//2負(fù)1正少漆，2正一負(fù)臼膏，一正一負(fù)一0，三個(gè)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個(gè)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標(biāo)在正,k標(biāo)在負(fù),j標(biāo)正0負(fù)都有
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){
//判斷結(jié)果集合中是否有List示损，去重
for(List<Integer> l : l2){
if(ListEqual(l, l1)) return true;
}
return false;
}
public boolean ListEqual(List<Integer> l1, List<Integer> l2){
//判斷兩個(gè)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;
}
}
