专业网站建设加盟合作,商务网站建设实训,seo快速排名培训,大连网站建设兼职问题描述
给定一个包含 n 个整数的数组 nums#xff0c;判断 nums 中是否存在三个元素 a#xff0c;b#xff0c;c #xff0c;使得 a b c 0 #xff1f;找出所有满足条件且不重复的三元组。
注意#xff1a;答案中不可以包含重复的三元组。 给定数组 nums [-1, 0,…问题描述
给定一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 找出所有满足条件且不重复的三元组。
注意答案中不可以包含重复的三元组。 给定数组 nums [-1, 0, 1, 2, -1, -4] 满足要求的三元组集合为 [ [-1, 0, 1], [-1, -1, 2] ] 解法一哈希表法 思路 首先对数组进行排序方便后续去重操作。遍历数组固定一个数 a 作为三元组中的第一个数。使用哈希集合来记录已经遍历过的数对于每个固定的 a遍历其后面的数 b计算 c -a - b如果哈希集合中包含 c则说明找到了一个满足条件的三元组。为了避免结果中出现重复的三元组需要对 a、b、c 进行去重处理。 代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;class Solution {public ListListInteger threeSum(int[] nums) {// 用于存储最终结果的列表ListListInteger result new ArrayList();// 对数组进行排序方便后续去重和处理Arrays.sort(nums);// 遍历数组固定第一个数 nums[i]for (int i 0; i nums.length; i) {// 如果第一个元素大于零由于数组已经排序后面的数也都大于零不可能凑成和为零的三元组if (nums[i] 0) {return result;}// 三元组元素 a 去重// 如果当前元素和前一个元素相同跳过当前元素避免重复结果if (i 0 nums[i] nums[i - 1]) {continue;}// 用于存储已经遍历过的数的哈希集合HashSetInteger set new HashSet();// 从 i1 开始遍历数组寻找第二个数 nums[j]for (int j i 1; j nums.length; j) {// 三元组元素 b 去重// 如果当前元素和前两个元素都相同跳过当前元素避免重复结果if (j i 2 nums[j] nums[j - 1] nums[j - 1] nums[j - 2]) {continue;}// 计算第三个数 c使得 a b c 0int c -nums[i] - nums[j];// 如果哈希集合中包含 c说明找到了一个满足条件的三元组if (set.contains(c)) {// 将三元组添加到结果列表中result.add(Arrays.asList(nums[i], nums[j], c));// 三元组元素 c 去重// 移除 c 以避免重复使用相同的 c 得到重复的三元组set.remove(c); } else {// 如果哈希集合中不包含 c将当前元素 nums[j] 添加到哈希集合中set.add(nums[j]);}}}return result;}
} 复杂度分析 时间复杂度(O(n^2))其中 n 是数组的长度。排序的时间复杂度为 (O(n log n))两层嵌套循环的时间复杂度为 (O(n^2))因此总的时间复杂度为 (O(n^2))。空间复杂度(O(n))主要用于存储哈希集合。 解法二双指针法 思路 同样先对数组进行排序。遍历数组固定一个数 a 作为三元组中的第一个数。对于每个固定的 a使用两个指针 left 和 right 分别指向 a 后面的元素和数组的最后一个元素。计算三个数的和 sum a b c根据 sum 的值移动指针 如果 sum 0说明 c 太大将 right 指针左移。如果 sum 0说明 b 太小将 left 指针右移。如果 sum 0说明找到了一个满足条件的三元组将其添加到结果列表中并对 b 和 c 进行去重处理然后继续移动指针寻找其他可能的三元组。 import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution {public ListListInteger threeSum(int[] nums) {// 用于存储最终结果的列表ListListInteger ret new ArrayList();// 对数组进行排序Arrays.sort(nums);// 遍历数组固定第一个数 nums[i]for (int i 0; i nums.length; i) {// 如果当前元素大于 0由于数组已排序后面的元素也都大于 0不可能找到和为 0 的三元组跳过此次循环if (nums[i] 0) {continue;}// 对第一个数去重避免结果中出现重复的三元组if (i 0 nums[i] nums[i - 1]) {continue;}// 左指针从 i1 开始int left i 1;// 右指针指向数组末尾int right nums.length - 1;while (left right) {// 计算三个数的和int sum nums[i] nums[left] nums[right];if (sum 0) {// 和小于 0左指针右移增大和left;} else if (sum 0) {// 和大于 0右指针左移减小和right--;} else {// 找到和为 0 的三元组添加到结果列表ret.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--;}}}return ret;}
} 复杂度分析 时间复杂度(O(n^2))其中 n 是数组的长度。排序的时间复杂度为 (O(n log n))外层循环遍历数组一次内层双指针遍历数组一次总的时间复杂度为 (O(n^2))。空间复杂度(O(log n)) 或 (O(n))取决于排序算法的实现。一般来说快速排序的空间复杂度为 (O(log n)) 总结 哈希表法利用哈希集合来记录已经遍历过的数通过查找哈希集合来判断是否存在满足条件的三元组实现相对简单但需要额外的空间来存储哈希集合。 双指针法通过排序和双指针的移动来寻找满足条件的三元组不需要额外的空间存储哈希集合空间复杂度较低是一种更优的解法。
在实际应用中建议优先使用双指针法来解决三数之和问题。
