力扣00015.三数之和

发表于 分类于 阅读次数： 本文字数： 2.5k 阅读时长 ≈ 9 分钟
三数之和、数组、双指针、排序、中等

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

  • $3 <= nums.length <= 3000$
  • $-10^5 <= nums[i] <= 10^5$

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        int length = nums.size();
        if (length < 3) {
            return result;
        }
        sort(nums.begin(), nums.end());
        for (int i = 0; i < length - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = length - 1;
            while (left < right) {
                int total = nums[i] + nums[left] + nums[right];
                if (total < 0) {
                    left++;
                } else if (total > 0) {
                    right--;
                } else {
                    result.push_back({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--;
                }
            }
        }
        return result;
    }
};

结果

执行用时 : 124 ms, 击败 58.25% 使用 C++ 的用户

内存消耗 : 23.80 MB, 击败 64.63% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int length = nums.length;
        if (length < 3) {
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i < length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = length - 1;
            while (left < right) {
                int total = nums[i] + nums[left] + nums[right];
                if (total < 0) {
                    left++;
                } else if (total > 0) {
                    right--;
                } else {
                    result.add(Arrays.asList(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--;
                }
            }
        }
        return result;
    }
}

结果

执行用时 : 32 ms, 击败 59.30% 使用 Java 的用户

内存消耗 : 49.95 MB, 击败 50.66% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def threeSum(self, nums):
        nums.sort()
        result = []
        length = len(nums)
        for i in range(length - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, length - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    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
        return result

结果

执行用时 : 716 ms, 击败 71.67% 使用 Python 的用户

内存消耗 : 18.73 MB, 击败 63.92% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        length = len(nums)
        for i in range(length - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, length - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    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
        return result

结果

执行用时 : 612 ms, 击败 92.99% 使用 Python3 的用户

内存消耗 : 20.02 MB, 击败 15.62% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int cmp(const void* pa, const void* pb){
    int a = *(int*)pa;
    int b = *(int*)pb;
    return a > b ? 1 : -1;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    int initialSize = 100;
    int** result = (int**)malloc(sizeof(int*) * initialSize);
    *returnColumnSizes = (int*)malloc(sizeof(int) * initialSize);
    *returnSize = 0;
    qsort(nums, numsSize, sizeof(int), cmp);
    for (int i = 0; i < numsSize - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1])
            continue;
        int left = i + 1;
        int right = numsSize - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result[*returnSize] = (int*)malloc(sizeof(int) * 3);
                (*returnColumnSizes)[*returnSize] = 3;
                result[*returnSize][0] = nums[i];
                result[*returnSize][1] = nums[left];
                result[*returnSize][2] = nums[right];
                (*returnSize)++;
                if (*returnSize == initialSize) {
                    initialSize *= 2;
                    result = (int**)realloc(result, sizeof(int*) * initialSize);
                    *returnColumnSizes = (int*)realloc(*returnColumnSizes, sizeof(int) * initialSize);
                }
                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;
}

结果

执行用时 : 276 ms, 击败 16.27% 使用 C 的用户

内存消耗 : 31.54 MB, 击败 68.67% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        Array.Sort(nums);
        IList<IList<int>> result = new List<IList<int>>();
        int length = nums.Length;
        for (int i = 0; i < length - 2; i++) {
            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
                int left = i + 1, right = length - 1, target = -nums[i];
                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum == target) {
                        result.Add(new List<int> { 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;
    }
}

结果

执行用时 : 180 ms, 击败 86.80% 使用 C# 的用户

内存消耗 : 73.13 MB, 击败 5.19% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    const length = nums.length;
    for (let i = 0; i < length - 2; i++) {
        if (i === 0 || (i > 0 && nums[i] !== nums[i - 1])) {
            let left = i + 1, right = length - 1, target = -nums[i];
            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;
};

结果

执行用时 : 152 ms, 击败 77.73% 使用 JavaScript 的用户

内存消耗 : 63.00 MB, 击败 6.25% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function threeSum(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const result: number[][] = [];
    const length = nums.length;
    for (let i = 0; i < length - 2; i++) {
        if (i === 0 || (i > 0 && nums[i] !== nums[i - 1])) {
            let left = i + 1, right = length - 1, target = -nums[i];
            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;
}

结果

执行用时 : 172 ms, 击败 45.17% 使用 TypeScript 的用户

内存消耗 : 63.81 MB, 击败 10.84% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function threeSum($nums) {
        $result = [];
        $length = count($nums);
        sort($nums);
        for ($i = 0; $i < $length - 2; $i++) {
            if ($i === 0 || ($i > 0 && $nums[$i] !== $nums[$i - 1])) {
                $left = $i + 1;
                $right = $length - 1;
                $target = -$nums[$i];
                while ($left < $right) {
                    $sum = $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;
    }
}

结果

执行用时 : 236 ms, 击败 72.28% 使用 PHP 的用户

内存消耗 : 26.17 MB, 击败 94.06% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var result = [[Int]]()
        let length = nums.count
        let sortedNums = nums.sorted()
        for i in 0..<length - 2 {
            if i == 0 || (i > 0 && sortedNums[i] != sortedNums[i - 1]) {
                var left = i + 1
                var right = length - 1
                let target = -sortedNums[i]
                while left < right {
                    let sum = sortedNums[left] + sortedNums[right]
                    if sum == target {
                        result.append([sortedNums[i], sortedNums[left], sortedNums[right]])
                        while left < right && sortedNums[left] == sortedNums[left + 1] {
                            left += 1
                        }
                        while left < right && sortedNums[right] == sortedNums[right - 1] {
                            right -= 1
                        }
                        left += 1
                        right -= 1
                    } else if sum < target {
                        left += 1
                    } else {
                        right -= 1
                    }
                }
            }
        }
        return result
    }
}

结果

执行用时 : 184 ms, 击败 37.55% 使用 Swift 的用户

内存消耗 : 19.67 MB, 击败 9.30% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {
        val result: MutableList<List<Int>> = mutableListOf()
        val length = nums.size
        val sortedNums = nums.sorted()
        for (i in 0 until length - 2) {
            if (i == 0 || (i > 0 && sortedNums[i] != sortedNums[i - 1])) {
                var left = i + 1
                var right = length - 1
                val target = -sortedNums[i]
                while (left < right) {
                    val sum = sortedNums[left] + sortedNums[right]
                    when {
                        sum == target -> {
                            result.add(listOf(sortedNums[i], sortedNums[left], sortedNums[right]))
                            while (left < right && sortedNums[left] == sortedNums[left + 1]) left++
                            while (left < right && sortedNums[right] == sortedNums[right - 1]) right--
                            left++
                            right--
                        }
                        sum < target -> left++
                        else -> right--
                    }
                }
            }
        }
        return result
    }
}

结果

执行用时 : 528 ms, 击败 42.86% 使用 Kotlin 的用户

内存消耗 : 54.28 MB, 击败 45.00% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  List<List<int>> threeSum(List<int> nums) {
    List<List<int>> result = [];
    nums.sort();
    for (int i = 0; i < nums.length - 2; i++) {
      if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
        int left = i + 1, right = nums.length - 1, target = -nums[i];
        while (left < right) {
          int sum = nums[left] + nums[right];
          if (sum == target) {
            result.add([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;
  }
}

结果

执行用时 : 396 ms, 击败 58.33% 使用 Dart 的用户

内存消耗 : 157.53 MB, 击败 75.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func threeSum(nums []int) [][]int {
    var result [][]int
    sort.Ints(nums)
    length := len(nums)
    for i := 0; i < length-2; i++ {
        if i == 0 || (i > 0 && nums[i] != nums[i-1]) {
            left, right := i+1, length-1
            target := -nums[i]
            for left < right {
                sum := nums[left] + nums[right]
                if sum == target {
                    result = append(result, []int{nums[i], nums[left], nums[right]})
                    for left < right && nums[left] == nums[left+1] {
                        left++
                    }
                    for left < right && nums[right] == nums[right-1] {
                        right--
                    }
                    left++
                    right--
                } else if sum < target {
                    left++
                } else {
                    right--
                }
            }
        }
    }
    return result
}

结果

执行用时 : 40 ms, 击败 90.27% 使用 Go 的用户

内存消耗 : 8.68 MB, 击败 35.24% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# @param {Integer[]} nums
# @return {Integer[][]}
def three_sum(nums)
    nums.sort!
    result = []
    (0..nums.length - 2).each do |i|
        if i == 0 || (i > 0 && nums[i] != nums[i - 1])
            left = i + 1
            right = nums.length - 1
            target = -nums[i]
            while left < right
                sum = nums[left] + nums[right]
                if sum == target
                    result << [nums[i], nums[left], nums[right]]
                    left += 1 while left < right && nums[left] == nums[left + 1]
                    right -= 1 while left < right && nums[right] == nums[right - 1]
                    left += 1
                    right -= 1
                elsif sum < target
                    left += 1
                else
                    right -= 1
                end
            end
        end
    end
    result
end

结果

执行用时 : 620 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 211.62 MB, 击败 16.67% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
object Solution {
  def threeSum(nums: Array[Int]): List[List[Int]] = {
    val sortedNums = nums.sorted
    val result = scala.collection.mutable.ListBuffer[List[Int]]()
    for (i <- 0 until sortedNums.length - 2) {
      if (i == 0 || (i > 0 && sortedNums(i) != sortedNums(i - 1))) {
        var left = i + 1
        var right = sortedNums.length - 1
        val target = -sortedNums(i)
        while (left < right) {
          val sum = sortedNums(left) + sortedNums(right)
          if (sum == target) {
            result += List(sortedNums(i), sortedNums(left), sortedNums(right))
            while (left < right && sortedNums(left) == sortedNums(left + 1)) left += 1
            while (left < right && sortedNums(right) == sortedNums(right - 1)) right -= 1
            left += 1
            right -= 1
          } else if (sum < target) {
            left += 1
          } else {
            right -= 1
          }
        }
      }
    }
    result.toList
  }
}

结果

执行用时 : 748 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 66.24 MB, 击败 85.71% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
impl Solution {
    pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = Vec::new();
        let mut nums = nums;
        nums.sort();
        for i in 0..nums.len() - 2 {
            if i == 0 || (i > 0 && nums[i] != nums[i - 1]) {
                let mut left = i + 1;
                let mut right = nums.len() - 1;
                let target = -nums[i];
                while left < right {
                    let sum = nums[left] + nums[right];
                    if sum == target {
                        result.push(vec![nums[i], nums[left], nums[right]]);
                        while left < right && nums[left] == nums[left + 1] {
                            left += 1;
                        }
                        while left < right && nums[right] == nums[right - 1] {
                            right -= 1;
                        }
                        left += 1;
                        right -= 1;
                    } else if sum < target {
                        left += 1;
                    } else {
                        right -= 1;
                    }
                }
            }
        }
        result
    }
}

结果

执行用时 : 32 ms, 击败 85.36% 使用 Rust 的用户

内存消耗 : 3.91 MB, 击败 67.78% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户