LeetCode - 三数之和题解

题目描述

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

解题思路

双指针法

var threeSum = function(nums) {
    let result = [];
    nums.sort((a, b) => a - b); // 先排序
    
    for(let i = 0; i < nums.length - 2; i++) {
        // 跳过重复值
        if(i > 0 && nums[i] === nums[i-1]) continue;
        
        let left = i + 1;
        let right = nums.length - 1;
        
        while(left < right) {
            let 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;
};

代码分析

1. 先对数组排序,便于去重和移动指针
2. 固定第一个数,使用双指针查找另外两个数
3. 注意跳过重复值,避免重复结果
4. 根据三数之和与0的关系移动指针

优化思路

1. 提前判断特殊情况:

   • 数组长度小于3
   • 最小三数之和大于0
   • 最大三数之和小于0

2. 剪枝优化:

   • 当 nums[i] > 0 时可以直接结束
   • 当 nums[i] + nums[i+1] + nums[i+2] > 0 时可以结束

复杂度分析

• 时间复杂度: O(n²)
• 空间复杂度: O(1)

参考资料

• LeetCode 15.三数之和
• 双指针技巧总结