LeetCode15.三数之和

LeetCode15.三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [   [-1, 0, 1],   [-1, -1, 2] ]

import java.util.*;/** * @author mac * @date 2020/11/5-22:57 */public class t15_三数之和 { /** * 遍历+双指针法 * 时间复杂度：O(n^2)，数组排序 O(NlogN)，遍历数组 O(n)， 双指针遍历 O(n) * 总体 O(NlogN)+O(n)∗O(n)=O(n2) * * @param nums * @return */ public List> threeSum(int[] nums) { // 对数组进行排序 Arrays.sort(nums); // 创建返回对象 List> res = new ArrayList<>(); // 循环遍历数组，因为是三数和，所以做后一个判断数组nums倒数第三个就可以了，故k < nums.length - 2 for (int k = 0; k < nums.length - 2; k++) { // 如果数组大于0了，就证明后面没有负数（提前排序过），那就不可能相加为0，故直接返回 if (nums[k] > 0) { break; } // 遍历第一个数时0<1，k-1就小于0，故有k > 0 ，前一个和后一个想等的话，那么只判断后面的就可以了，两个都判断如果有三数和为0，接过重复 if (k > 0 && nums[k] == nums[k - 1]) { continue; } // i指针1在k前一位，j指针有最后一位 int i = k + 1, j = nums.length - 1; // 如果大于等于j，那么证明两个指针碰撞了，就不需要继续判断三数之和了 while (i < j) { // 三数相加 int sum = nums[k] + nums[i] + nums[j]; // 因为最开始是排序过的，如果三数和小于0，那么i需要右→移去更大的数 if (sum < 0) { // 如i和i右面的数相同，就没有再去判断的必要了 while (i < j && nums[i] == nums[++i]) ; } // // 因为最开始是排序过的，如果三数和大于0，那么j需要左←移去更小的数 else if (sum > 0) { // 如j和j左面的数相同，就没有再去判断的必要了 while (i < j && nums[j] == nums[--j]) ; } else { // 满足三数和为0,存放在结果集中 res.add(new ArrayList(Arrays.asList(nums[k], nums[i], nums[j]))); // 可能存在多组解，同时去除重复接，并同时将 i，j移到下一位置，寻找新的解 while (i < j && nums[i] == nums[++i]) ; while (i < j && nums[j] == nums[--j]) ; } } } return res; } /** * 超出时间限制，时间复杂度 O(n^2) * 双重暴力+hash */ public static List> threeSum1(int[] nums) { // 如果数组的长度小于2，一定没有满足条件的集合 if (nums == null || nums.length <= 2) { return Collections.emptyList(); } // 排序 Arrays.sort(nums); // 使用Set防重，对结果防重 Set> result = new LinkedHashSet<>(); // 遍历数组 for (int i = 0; i < nums.length - 2; i++) { // 使用Hash表存储数据， Map hashMap = new HashMap<>(); for (int j = i + 1; j < nums.length; j++) { // 如果为没有两数之和等于第三个数的相反数，就不满足三数之和为0的条件 if (hashMap.get(-nums[i] - nums[j]) != null) { // 把满足条件数据生成集合 List list = Arrays.asList(nums[i], hashMap.get(-nums[i] - nums[j]), nums[j]); // 对集合进行排序，防止 [1,0,-1] [-1,0,1]去不掉 Collections.sort(list); // 放入Set中，对结果进行去重 result.add(list); } else { // 将不满足的条件的存储在hash表中（有可能是数据不够，或者没有满足条件的数据） hashMap.put(nums[j], nums[j]); } } } // 转成集合返回 return new ArrayList<>(result); } /** * 超出时间限制，时间复杂度 O(n^3) */ public static List> threeSum2(int[] nums) { // 如果数组的长度小于2，一定没有满足条件的集合 if (nums == null || nums.length <= 2) { return Collections.emptyList(); } // 排序 // 使用Set防重，对结果防重 Set> result = new LinkedHashSet<>(); // 三重for循环 for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { for (int k = j + 1; k < nums.length; k++) { // 如果满足三数和是0 if (nums[i] + nums[j] + nums[k] == 0) { // 把满足条件数据生成集合 List value = Arrays.asList(nums[i], nums[j], nums[k]); // 放入Set中 result.add(value); } } } } // 转成集合返回 return new ArrayList<>(result); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。