【LeetCode】15. 三数之和（似NC54）

一、题目

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

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：
[[-1, 0, 1],[-1, -1, 2]
]

二、解决

1、暴力

思路： 三重循环，遇到三值之和为0的，记录下数值，循环完毕后，返回数值。
代码： 略，有兴趣可看参考1。
时间复杂度： O( n 3 n^3 n3)
空间复杂度： O(n)

2、Set查询

思路： a+b+c=0 --> c = -(a+b)，a、b两个数使用两层遍历（ 复杂度O( n 2 n^2 n2) )，对c使用set查询O(1)。
代码： 略，待补充。
时间复杂度： O( n 2 n^2 n2)
空间复杂度： O(n)

3、夹逼法

思路： 可看参考5.
代码：

class Solution {public List<List<Integer>> threeSum(int[] nums) {if (nums.length < 3) return new ArrayList<>(); // if nums less than 3 elementArrays.sort(nums); // sort arraySet<List<Integer>> result = new HashSet<>();for (int i = 0; i < nums.length - 2; i++) {int low = i + 1;int high = nums.length - 1;while (low < high) {int sum = nums[i] + nums[low] + nums[high];if (sum == 0) result.add(Arrays.asList(nums[i], nums[low++], nums[high--]));else if (sum > 0) high--;else if (sum < 0) low++;}}return new ArrayList<>(result);}
}

时间复杂度： O( n 2 n^2 n2)
空间复杂度： O(1)

三、NC54

1、夹逼法

思路： 同上。
代码：

import java.util.*;public class Solution {public ArrayList<ArrayList<Integer>> threeSum(int[] num) {ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();if (num.length < 3) return res;Arrays.sort(num);for (int i = 0; i < num.length - 2; i++) {if (i > 0 && num[i] == num[i-1]) continue;int low = i + 1, high = num.length - 1;while (low < high) {int sum = num[i] + num[low] + num[high];if (sum == 0) {ArrayList<Integer> tmp = new ArrayList<>();tmp.add(num[i]);tmp.add(num[low]);tmp.add(num[high]);res.add(tmp);while (low < high && num[low] == tmp.get(1)) low++;} else if (sum > 0) high--;else low++;}}return res;}
}

时间复杂度： O( n 2 n^2 n2)
空间复杂度： O(1)

四、参考

1、15. 三数之和，Java简洁题解（暴力、hash、双指针）
2、Concise O(N^2) Java solution
3、Iterative & Recursive | Detailed Steps of 2-Pointers Dry Run and Clean Code
4、Java Arrays.asList()方法详解
5、三数之和（排序+双指针，易懂图解）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！