当前位置: 首页> 游戏> 评测 > 甘肃疫情最新消息今天50例_设计公司企业想法描述_seo和竞价排名的区别_北京seo公司哪家好

甘肃疫情最新消息今天50例_设计公司企业想法描述_seo和竞价排名的区别_北京seo公司哪家好

时间:2025/7/28 8:18:29来源:https://blog.csdn.net/hqy1989/article/details/146430892 浏览次数:0次
甘肃疫情最新消息今天50例_设计公司企业想法描述_seo和竞价排名的区别_北京seo公司哪家好

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

方法一:暴力枚举法

该方法通过三重循环遍历数组中所有可能的三元组组合,计算它们的和是否为 0,同时使用集合来避免结果中出现重复的三元组。

function threeSum(nums: number[]): number[][] {const result: number[][] = [];const n = nums.length;const uniqueSet = new Set<string>();for (let i = 0; i < n; i++) {for (let j = i + 1; j < n; j++) {for (let k = j + 1; k < n; k++) {if (nums[i] + nums[j] + nums[k] === 0) {const triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);const key = triplet.join(',');if (!uniqueSet.has(key)) {result.push(triplet);uniqueSet.add(key);}}}}}return result;
}
复杂度分析
  • 时间复杂度:(O(n^3)),因为使用了三重嵌套循环来遍历所有可能的三元组组合,n 是数组的长度。
  • 空间复杂度:(O(m)),其中 m 是满足条件的三元组的数量,主要用于存储结果和去重集合。

方法二:排序 + 双指针法

首先对数组进行排序,然后固定一个数,使用双指针在剩余的数中寻找另外两个数,使得它们的和等于固定数的相反数。同时,在遍历过程中跳过重复的元素,避免结果中出现重复的三元组。

function threeSum(nums: number[]): number[][] {const result: number[][] = [];const n = nums.length;nums.sort((a, b) => a - b);for (let i = 0; i < n - 2; i++) {if (i > 0 && nums[i] === nums[i - 1]) {continue;}const target = -nums[i];let left = i + 1;let right = n - 1;while (left < right) {const sum = nums[left] + nums[right];if (sum === target) {result.push([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 < target) {left++;} else {right--;}}}return result;
}
复杂度分析
  • 时间复杂度:(O(n^2)),排序的时间复杂度为 (O(n log n)),双指针遍历的时间复杂度为 (O(n^2)),因此总的时间复杂度为 (O(n^2))。
  • 空间复杂度:(O(log n)) 到 \(O(n)),主要取决于排序算法的空间复杂度。

方法三:哈希表法

使用哈希表来记录每个数出现的次数,然后固定两个数,通过哈希表查找第三个数是否存在,同时要注意处理重复元素和避免重复的三元组。

function threeSum(nums: number[]): number[][] {const result: number[][] = [];const n = nums.length;const numCountMap = new Map<number, number>();for (const num of nums) {numCountMap.set(num, (numCountMap.get(num) || 0) + 1);}const uniqueNums = Array.from(numCountMap.keys()).sort((a, b) => a - b);const uniqueN = uniqueNums.length;for (let i = 0; i < uniqueN; i++) {for (let j = i; j < uniqueN; j++) {const num1 = uniqueNums[i];const num2 = uniqueNums[j];const num3 = -(num1 + num2);if (num3 < num2) {break;}if (!numCountMap.has(num3)) {continue;}let count = numCountMap.get(num3)!;if (num1 === num2) {count--;}if (num2 === num3) {count--;}if (num1 === num3) {count--;}if (count >= 0) {const triplet = [num1, num2, num3].sort((a, b) => a - b);const key = triplet.join(',');const isDuplicate = result.some((res) => res.join(',') === key);if (!isDuplicate) {result.push(triplet);}}}}return result;
}
复杂度分析
  • 时间复杂度:(O(n^2)),需要两层嵌套循环来固定两个数,然后在哈希表中查找第三个数。
  • 空间复杂度:(O(n)),主要用于存储哈希表。

你可以使用以下方式测试这些函数:

const nums = [-1, 0, 1, 2, -1, -4];
console.log(threeSum(nums));

综上所述,排序 + 双指针法是解决该问题的较为高效的方法,时间复杂度和空间复杂度都相对较好。

关键字:甘肃疫情最新消息今天50例_设计公司企业想法描述_seo和竞价排名的区别_北京seo公司哪家好

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: