15. 三数之和(左右指针)

算法分析：

• 数组排序：先将数组排序，时间复杂度 O(NlogN)。

• 固定一个数，双指针查找：

  • 用一个循环固定第一个数 nums[i]。
  • 在剩余的部分，使用双指针 left 和 right 来寻找符合条件的三元组。

• 跳过重复元素(注意)：

  • 如果 nums[i] 与前一个元素相同，跳过，避免重复三元组。
  • 找到三元组后，分别跳过相同的 left 和 right 元素，防止重复。

• 双指针移动逻辑：

  • 和小于0：left++，增大和。
  • 和大于0：right--，减小和。
  • 和等于0：保存三元组，同时移动 left++ 和 right--，继续查找。

代码： 

import java.util.*;class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums); // 使用正确的 Arrays.sort()List<List<Integer>> ans = new ArrayList<>(); // 用于存储结果的列表for (int i = 0; i < nums.length - 2; i++) {// 跳过相同的元素以避免重复三元组if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = nums.length - 1;while (left < right) { // 使用 left < right，而不是 left <= rightint sum = nums[i] + nums[left] + nums[right];if (sum == 0) {// 找到符合条件的三元组，保存到结果列表ans.add(Arrays.asList(nums[i], nums[left], nums[right]));// 跳过相同的 left 和 right 元素，避免重复while (left < right && nums[left] == nums[left + 1]) {left++;}while (left < right && nums[right] == nums[right - 1]) {right--;}// 移动指针寻找新的组合left++;right--;} else if (sum < 0) {left++; // 如果和小于 0，增加 left} else {right--; // 如果和大于 0，减小 right}}}return ans;}
}