2020-ARTS-打卡第十三天
Algorithm 题目 题目描述 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。答案中不可以包含重复的三元组。 题目解答 import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); if(null == nums || nums.length < 3) { return result; } Arrays.sort(nums); for (int i = 0; i < nums.length; i ++) { if(nums[i] > 0) { break; } if(i > 0 && nums[i] == nums[i - 1]) { continue; } int L = i + 1; int R = nums.length - 1; while (L < R) { int target = nums[i] + nums[L] + nums[R]; if (target == 0) { result.add(Arrays.asList(nums[i], nums[L], nums[R])); while (L < R && nums[L] == nums[L + 1]) L++; while (L < R && nums[R] == nums[R - 1]) R--; L++; R--; } else if (target < 0) { L++; } else { R--; } } } return result; } 一共有三种解法，一是三层for循环，时间复杂度为O(n3)；二是二层for循环外加Hash表，时间复杂度为O(n2)，增加了空间复杂度O(n);第三种就是上面的解法，排序后从两侧开始匹配，时间复杂度为O(n2)，空间复杂度为O(1) ...