LeetCode15:三数之和
- 首先对数组进行排序，这是使用双指针技术的前提，也有助于去重
- 固定第一个元素（i位置），然后用左右双指针寻找另外两个元素
- 通过三数之和与0的比较来移动指针：
- 和为0时，记录结果并跳过重复元素
- 和小于0时，右移左指针增大总和
- 和大于0时，左移右指针减小总和
- 利用排序后的特性，通过比较相邻元素跳过重复解
算法的时间复杂度为O(n²)，其中排序占O(n log n)，主体双指针遍历占O(n²)；空间复杂度为O(1)（不包括存储结果的空间）。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class ThreeSum {public List<List<Integer>> threeSum(int[] nums) {// 创建结果列表List<List<Integer>> result = new ArrayList<>();// 处理边界情况if (nums == null || nums.length < 3) {return result;}// 排序数组，便于去重和双指针操作Arrays.sort(nums);// 遍历每个可能的第一个元素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) {int sum = nums[i] + nums[left] + nums[right];if (sum == 0) {// 找到符合条件的三元组，添加到结果中result.add(Arrays.asList(nums[i], nums[left], nums[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) {// 和小于0，需要增大总和，移动左指针left++;} else {// 和大于0，需要减小总和，移动右指针right--;}}}return result;}// 测试方法public static void main(String[] args) {ThreeSum solution = new ThreeSum();// 测试用例int[][] testCases = {{-1, 0, 1, 2, -1, -4},{},{0},{0, 0, 0}};// 输出测试结果for (int[] testCase : testCases) {System.out.println("输入: " + Arrays.toString(testCase));System.out.println("输出: " + solution.threeSum(testCase));System.out.println();}}
}