LeetCode 热题 100 —— 6.三数之和（Javascript解法）

一、题目要求

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

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

二、题目思路

解法：排序 + 双指针

1.先对数组排序，便于去重和双指针移动；

2.固定一个数 nums[i]，然后在 i 右侧使用双指针寻找两数之和等于 -nums[i]

3.跳过重复元素，保证结果不重复

三、代码实现

/** * @param {number[]} nums * @return {number[][]} */ var threeSum = function(nums) { //边界控制（数组长度小于3直接返回空值） if(nums.length < 3) return[]; //排序（升序） nums.sort((a,b) => a-b); let result = []; const n = nums.length; for(let i = 0; i < n-2; i++){ // 优化：如果当前最小的数都大于 0，三数之和不可能为 0，直接终止循环 if (nums[i] > 0) break; // 跳过重复的 i，避免产生重复的三元组 if (i > 0 && nums[i] === nums[i - 1]) continue; let left = i + 1; let right = n - 1; while(left < right){ const sum = nums[i] + nums[left] + nums[right]; if(sum == 0){ // 找到一个合法三元组 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 < 0 ){ // 和太小，左指针右移增大和 left++; }else{ //和太大，右指针左移减小和 right--; } } } return result; };

四、总结

该算法时间复杂度为O(n²)。