我的解法（不是完全解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;
  }