题目描述

三数之和

给定一个包含n个整数的数组nums，以及一个目标值target，找出数组中所有三个数的所有独特组合，使得这三个数之和等于target。

注意：

• 解答中不能包含重复的三元组。
• 你可以按任意顺序返回答案。

示例

示例 1:

输入: nums = [-1, 0, 1, 2, -1, -4], target = 0
输出: [[-1, 0, 1], [-1, -1, 2]]

示例 2:

输入: nums = [], target = 0
输出: []

示例 3:

输入: nums = [0], target = 0
输出: []

PHP 代码示例

function threeSum($nums, $target) {
    $result = [];
    sort($nums); // 先对数组进行排序
    $length = count($nums);
    
    for ($i = 0; $i < $length - 2; $i++) {
        // 跳过重复元素
        if ($i > 0 && $nums[$i] == $nums[$i - 1]) {
            continue;
        }
        
        $left = $i + 1;
        $right = $length - 1;
        
        while ($left < $right) {
            $sum = $nums[$i] + $nums[$left] + $nums[$right];
            
            if ($sum == $target) {
                $result[] = [$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--;
            } elseif ($sum < $target) {
                $left++;
            } else {
                $right--;
            }
        }
    }
    
    return $result;
}

// 示例调用
$nums = [-1, 0, 1, 2, -1, -4];
$target = 0;
$result = threeSum($nums, $target);
print_r($result);

Python 代码示例

def threeSum(nums, target):
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, n - 1
        
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == target:
                result.append([nums[i], nums[left], nums[right]])
                
                # 跳过重复元素
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                
                left += 1
                right -= 1
            elif s < target:
                left += 1
            else:
                right -= 1
    
    return result

# 示例调用
nums = [-1, 0, 1, 2, -1, -4]
target = 0
result = threeSum(nums, target)
print(result)

JavaScript 代码示例

function threeSum(nums, target) {
    nums.sort((a, b) => a - b);
    const result = [];
    const n = nums.length;

    for (let i = 0; i < n - 2; 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 === 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;
}

// 示例调用
const nums = [-1, 0, 1, 2, -1, -4];
const target = 0;
const result = threeSum(nums, target);
console.log(result);

在以上示例中，我们首先对数组进行排序，然后使用双指针技巧来寻找三数之和等于目标值的组合，并跳过重复元素以避免重复的组合出现在结果中。这种方法的时间复杂度为O(n^2)，空间复杂度主要取决于结果数组的大小，最坏情况下为O(n^2)，但通常会更小。