思路
- 排序:首先对数组进行排序,这样可以保证在遍历过程中,相同的元素会相邻,同时也方便使用双指针法。
避免重复:在遍历过程中,如果当前元素与前一个元素相同,则跳过当前元素,以避免生成重复的三元组。
边界条件:在开始寻找三元组之前,检查当前元素是否大于0,如果是,则直接返回结果,因为不可能有三数之和为0。
跳过相同元素:在找到和为0的三元组后,需要跳过所有相同的元素,以避免生成重复的三元组。
详细步骤
排序数组:
- 使用
nums.sort((a, b) => a - b)
对数组nums
进行排序。这是一个数值排序,确保数组按照从小到大的顺序排列。- 排序的目的是为了后续使用双指针法,这样可以保证在寻找三元组时,如果一个元素比前一个元素大,那么它后面所有的元素都会比前一个元素大,从而避免生成重复的三元组。
遍历数组:
- 通过
for
循环遍历数组nums
,变量i
作为当前索引。- 在每次迭代开始时,检查当前元素
nums[i]
是否大于0。如果是,由于数组已经排序,所有后续元素都将是正数,不可能找到和为0的三元组,因此直接返回空数组res
。跳过重复元素:
- 在遍历过程中,如果当前元素
nums[i]
与前一个元素nums[i-1]
相同,则跳过当前迭代。这是为了避免生成重复的三元组,因为排序后的数组中相同的元素是连续的。初始化左右指针:
- 对于每个未跳过的元素
nums[i]
,初始化两个指针:left
指向i+1
(当前元素之后的下一个元素),right
指向数组的最后一个元素。- 这三个索引
i
、left
和right
将用于寻找和为0的三元组。双指针法寻找三元组:
- 使用
while
循环,同时移动left
和right
指针来寻找和为0的三元组。- 在循环中,计算三个指针所指向元素的和:
sum = nums[i] + nums[left] + nums[right]
。- 如果
sum < 0
,则left
指针向右移动一位,因为需要一个更大的数来增加总和。- 如果
sum > 0
,则right
指针向左移动一位,因为需要一个更小的数来减少总和。- 如果
sum === 0
,则找到了一个和为0的三元组,将其添加到结果数组res
中。跳过重复的三元组:
- 在找到和为0的三元组后,需要跳过所有重复的元素,以避免生成重复的三元组。
- 通过两个
while
循环,分别跳过left
指针左侧和right
指针右侧的所有重复元素。移动指针继续寻找:
- 在每次找到和为0的三元组后,
left
和right
指针分别向右和向左移动一位,继续寻找下一个可能的三元组。返回结果:
- 遍历完成后,返回包含所有不重复三元组的结果数组
res
。
题目
示例代码
javascript">var threeSum = function(nums) {// 初始化结果数组 res,用于存储满足条件的三元组const res = [];// 获取数组的长度const len = nums.length;// 对数组进行从小到大排序nums.sort((a, b) => a - b);// 遍历数组,从索引0开始,直到数组的最后一个元素for (let i = 0; i < len; i++) {// 初始化左右指针,分别指向当前元素之后的元素和数组的最后一个元素let left = i + 1, right = len - 1, iNum = nums[i];// 如果当前元素大于0,那么左右指针的值也大于0,三者和不会为0(数组已排序)if (iNum > 0) return res;// 如果当前元素与前一个元素相同,则跳过,以避免重复的三元组if (i === 0 || nums[i] != nums[i - 1]) {// 使用 while 循环,通过移动左右指针来寻找和为0的三元组while (left < right) {let lNum = nums[left], rNum = nums[right], sum = iNum + lNum + rNum;// 如果三元组的和小于0,移动左指针以增加三元组的和if (sum < 0) left++;// 如果三元组的和大于0,移动右指针以减少三元组的和else if (sum > 0) right--;// 如果三元组的和正好为0,找到了一个满足条件的三元组else {// 将当前三元组添加到结果数组中res.push([iNum, lNum, rNum]);// 移动左指针,跳过所有相同的元素,以避免重复的三元组while (left < right && nums[left] === nums[left + 1]) {left++;}// 移动右指针,跳过所有相同的元素,以避免重复的三元组while (left < right && nums[right] === nums[right - 1]) {right--;}// 移动左指针和右指针,继续寻找下一个可能的三元组left++;right--;}}}}// 返回包含所有满足条件的三元组的结果数组return res;
};
欢迎指正!