我的解法（不是完全解309/314）

• 我的思路是定義一個left和一個right，然后在向集合里去查詢，看看有沒有除了nums[left]，和nums[right]的第三個元素，把這個問題轉換為一個遍歷查找問題

  • 利用List.contains()方法來查找剩余元素
  • 利用List.remove和List.add()，來模擬派出了nums[left]和nums[right]的集合

• 但是這種思路有個問題，就是時間復雜度太高了，我只通過了309/314的示例。

  • 其中這個ArrayList.contains 是 O(n)，ArrayList.remove(Integer) 也是 O(n)，然后外層有一個從left-length，有一個從length-left，循環接近O(n³)，時間復雜度太高了

  • int left = 0,right =0;
    ArrayList<Integer> list = new ArrayList<>();
    for(int num:nums){list.add(num);
    }
    List<List<Integer>> result = new ArrayList<>();
    for(;left<nums.length-2;left++){list.remove(Integer.valueOf(nums[left]));List<Integer> temp = new ArrayList<>();int a =0;for(right=nums.length-1;right>left;right--){list.remove(Integer.valueOf(nums[right]));a = 0-nums[left]-nums[right];if(list.contains(a)){Collections.addAll(temp,nums[left],nums[right],a);List<Integer> temp2 = new ArrayList<>(temp);Collections.sort(temp2);if(!result.contains(temp2)){result.add(temp2);}temp.clear();}list.add(nums[right]);}
    }
    return result;
    

• 改進1：對于這個代碼我們需要想辦法減少它的時間復雜度，為了遍歷出所有情況，內外兩層循環遍歷是不能夠改變的。所以我們可以想辦法去減少這個查找的時間復雜度，將這個集合轉換為哈希集合，這樣查詢的時間復雜度就變成了O(1)了

  • 但是很遺憾，這個時間復雜度還是高了，還需要繼續降時間復雜度

  • List<List<Integer>> result = new ArrayList<>();
    // 用 HashMap 統計每個數字的出現次數（替代 ArrayList）
    Map<Integer, Integer> count = new HashMap<>();
    for (int num : nums) {count.put(num, count.getOrDefault(num, 0) + 1);
    }
    // 為了去重，排序后按順序枚舉
    int n = nums.length;
    for (int i = 0; i < n - 2; i++) {int left = nums[i];count.put(left, count.get(left) - 1); // 用掉一個 leftfor (int j = n-1; j >i; j--) {int right = nums[j];count.put(right, count.get(right) - 1); // 用掉一個 rightint target = 0 - left - right;// 檢查剩余集合中是否有 targetif (count.getOrDefault(target, 0) > 0) {List<Integer> list = Arrays.asList(left, right, target);Collections.sort(list); // 排序以確保結果的唯一性if (!result.contains(list)) {result.add(list);}}// 把 right 加回來，供下一輪使用count.put(right, count.get(right) + 1);}
    }
    return result;
    

靈神的思路

• 靈神在講這個題的時候先參考了這個 📄((20250730131645-jdjxatg ‘0167 兩數之和II-輸入有序數組’)) 這個題
  如果是兩個數的話，我們就可以使用兩個指針進行快速的尋找
  所以我們想想辦法，看怎么使這個三個數的和變成兩個數

• 我們可以通過先對這個數組進行排序，這樣就和0167題具有了相同的初始條件，即數組有序
  之后我們對這個數組進行遍歷，先確定一個數，之后再剩余的數組中，找到兩個數的和為0-這個數，此時就和0167題相似了。

• 有一個點，不太容易理解，就是為什么left是從i+1開始，而不是從別的地方開始
  是因為，每次遍歷的時候，都會把這個位置的所有情況給考慮到，后續的其它集合就不會包含這個元素

  //講數組進行排序
  Arrays.sort(nums);
  int n = nums.length;
  List<List<Integer>> ans = new ArrayList<>();
  for( int i= 0; i<n-2;i++){if(i>0&&nums[i]==nums[i-1]){continue;//代表這個重復了}int left = i+1;int right= n-1;int target = 0 - nums[i];while(left<right){if(nums[left]+nums[right]>target){right--;}else if(nums[left]+nums[right]<target){left++;}else {ans.add(Arrays.asList(nums[i], nums[left], nums[right]));//之后的話進行下一輪，因為可能還有重復,我們將left和right修改//比如[-2,-2,-2,-2,4,4,4,4,4],這個地方就有可能重復left++;while(left<right&&nums[left]==nums[left-1]){left++;}right--;while(left<right&&nums[right]==nums[right+1]) {right--;}}}
  }
  return ans;
  

• 如何剪枝
  當我們確定了第一個數，發現它和這個排序后的數組中最大的兩個數相加都小于0的話，那么這個都不用看了，不可能會有等于0的情況，我們此時切換到下一個數
  當我們確定了第一個數，如果它和它緊挨著的兩個數（靠近它最小的數）相加大于0，那么后續都會大于0，直接跳過

• if(nums[i]+nums[i+1]+nums[i+2]>0){break;
  }
  if(nums[i]+nums[n-1]+nums[n-2]<0){continue;
  }