力扣00018.四数之和

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

题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

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

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

  • $1 <= nums.length <= 200$
  • $-10^9 <= nums[i] <= 10^9$
  • $-10^9 <= target <= 10^9$

解决方法

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
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        int n = nums.size();
        if (n < 4) {
            return result;
        }
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 3; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < n - 2; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    long long sum = static_cast<long long>(nums[i]) + static_cast<long long>(nums[j]) + static_cast<long long>(nums[left]) + static_cast<long long>(nums[right]);
                    if (sum == target) {
                        result.push_back({nums[i], nums[j], 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;
    }
};

结果

执行用时 : 72 ms, 击败 56.26% 使用 C++ 的用户

内存消耗 : 13.43 MB, 击败 19.12% 使用 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> quadruplets = new ArrayList<>();
        if (nums == null || nums.length < 4) {
            return quadruplets;
        }
        Arrays.sort(nums);
        int length = nums.length;
        for (int i = 0; i < length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
                continue;
            }
            for (int j = i + 1; j < length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                    continue;
                }
                int left = j + 1, right = length - 1;
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        left++;
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return quadruplets;
    }
}

结果

执行用时 : 2 ms, 击败 99.83% 使用 Java 的用户

内存消耗 : 42.84 MB, 击败 46.30% 使用 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
25
26
27
28
29
30
31
32
33
34
35
36
class Solution(object):
    def fourSum(self, nums, target):
        quadruplets = []
        nums.sort()
        length = len(nums)
        for i in range(length - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
                break
            if nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target:
                continue
            for j in range(i + 1, length - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
                    break
                if nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target:
                    continue
                left = j + 1
                right = length - 1
                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    if total == target:
                        quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        right -= 1
                    elif total < target:
                        left += 1
                    else:
                        right -= 1
        return quadruplets

结果

执行用时 : 40 ms, 击败 96.53% 使用 Python 的用户

内存消耗 : 12.91 MB, 击败 85.86% 使用 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
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        length = len(nums)
        quadruplets = []
        for i in range(length - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
                break
            if nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target:
                continue
            for j in range(i + 1, length - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
                    break
                if nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target:
                    continue
                left = j + 1
                right = length - 1
                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    if total == target:
                        quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        right -= 1
                    elif total < target:
                        left += 1
                    else:
                        right -= 1
        return quadruplets

结果

执行用时 : 56 ms, 击败 98.70% 使用 Python3 的用户

内存消耗 : 17.07 MB, 击败 12.39% 使用 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
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), compare);
    int capacity = 16;
    int** result = (int**)malloc(capacity * sizeof(int*));
    *returnColumnSizes = (int*)malloc(capacity * sizeof(int));
    *returnSize = 0;
    for (int i = 0; i < numsSize - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        for (int j = i + 1; j < numsSize - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }
            int left = j + 1;
            int right = numsSize - 1;
            while (left < right) {
                long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    if (*returnSize == capacity) {
                        capacity *= 2;
                        result = (int**)realloc(result, capacity * sizeof(int*));
                        *returnColumnSizes = (int*)realloc(*returnColumnSizes, capacity * sizeof(int));
                    }
                    result[*returnSize] = (int*)malloc(4 * sizeof(int));
                    result[*returnSize][0] = nums[i];
                    result[*returnSize][1] = nums[j];
                    result[*returnSize][2] = nums[left];
                    result[*returnSize][3] = nums[right];
                    (*returnColumnSizes)[*returnSize] = 4;
                    (*returnSize)++;
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    left++;
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return result;
}

结果

执行用时 : 36 ms, 击败 25.54% 使用 C 的用户

内存消耗 : 7.29 MB, 击败 94.96% 使用 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution
{
    public IList<IList<int>> FourSum(int[] nums, int target)
    {
        Array.Sort(nums);
        IList<IList<int>> result = new List<IList<int>>();
        for (int i = 0; i < nums.Length - 3; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            for (int j = i + 1; j < nums.Length - 2; j++)
            {
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;
                int left = j + 1;
                int right = nums.Length - 1;
                while (left < right)
                {
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target)
                    {
                        result.Add(new List<int> { nums[i], nums[j], 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;
    }
}

结果

执行用时 : 124 ms, 击败 97.50% 使用 C# 的用户

内存消耗 : 46.96 MB, 击败 9.38% 使用 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
30
31
32
33
34
35
36
37
38
39
40
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    nums.sort((a, b) => a - b);
    const result = [];
    for (let i = 0; i < nums.length - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        for (let j = i + 1; j < nums.length - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) {
                continue;
            }
            let left = j + 1;
            let right = nums.length - 1;
            while (left < right) {
                const sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum === target) {
                    result.push([nums[i], nums[j], nums[left], nums[right]]);
                    while (left < right && nums[left] === nums[left + 1]) {
                        left++;
                    }
                    left++;
                    while (left < right && nums[right] === nums[right - 1]) {
                        right--;
                    }
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return result;
};

结果

执行用时 : 96 ms, 击败 34.66% 使用 JavaScript 的用户

内存消耗 : 52.09 MB, 击败 12.46% 使用 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
26
27
28
29
30
31
32
33
34
35
function fourSum(nums: number[], target: number): number[][] {
    nums.sort((a, b) => a - b);
    const result: number[][] = [];
    for (let i = 0; i < nums.length - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        for (let j = i + 1; j < nums.length - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) {
                continue;
            }
            let left = j + 1;
            let right = nums.length - 1;
            while (left < right) {
                const sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum === target) {
                    result.push([nums[i], nums[j], nums[left], nums[right]]);
                    while (left < right && nums[left] === nums[left + 1]) {
                        left++;
                    }
                    left++;
                    while (left < right && nums[right] === nums[right - 1]) {
                        right--;
                    }
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return result;
}

结果

执行用时 : 108 ms, 击败 21.46% 使用 TypeScript 的用户

内存消耗 : 53.43 MB, 击败 7.32% 使用 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
35
36
37
38
39
40
41
42
43
44
class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[][]
     */
    function fourSum($nums, $target) {
        sort($nums);
        $result = [];
        $length = count($nums);
        for ($i = 0; $i < $length - 3; $i++) {
            if ($i > 0 && $nums[$i] == $nums[$i - 1]) {
                continue;
            }
            for ($j = $i + 1; $j < $length - 2; $j++) {
                if ($j > $i + 1 && $nums[$j] == $nums[$j - 1]) {
                    continue;
                }
                $left = $j + 1;
                $right = $length - 1;
                while ($left < $right) {
                    $sum = $nums[$i] + $nums[$j] + $nums[$left] + $nums[$right];
                    if ($sum == $target) {
                        $result[] = [$nums[$i], $nums[$j], $nums[$left], $nums[$right]];
                        while ($left < $right && $nums[$left] == $nums[$left + 1]) {
                            $left++;
                        }
                        $left++;
                        while ($left < $right && $nums[$right] == $nums[$right - 1]) {
                            $right--;
                        }
                        $right--;
                    } elseif ($sum < $target) {
                        $left++;
                    } else {
                        $right--;
                    }
                }
            }
        }
        return $result;
    }
}

结果

执行用时 : 188 ms, 击败 25.00% 使用 PHP 的用户

内存消耗 : 19.44 MB, 击败 12.50% 使用 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
34
35
36
37
class Solution {
  func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
      var result = [[Int]]()
      let sortedNums = nums.sorted()
      for k in 0..<sortedNums.count {
          if k > 0 && sortedNums[k] == sortedNums[k - 1] {
              continue
          }
          for i in (k + 1)..<sortedNums.count {
              if i > k + 1 && sortedNums[i] == sortedNums[i - 1] {
                  continue
              }
              var left = i + 1
              var right = sortedNums.count - 1
              while left < right {
                  let sum = sortedNums[k] + sortedNums[i] + sortedNums[left] + sortedNums[right]
                  if sum < target {
                      left += 1
                  } else if sum > target {
                      right -= 1
                  } else {
                      result.append([sortedNums[k], 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
                  }
              }
          }
      }
      return result
  }
}

结果

执行用时 : 24 ms, 击败 62.86% 使用 Swift 的用户

内存消耗 : 15.23 MB, 击败 22.86% 使用 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
30
31
32
33
34
35
36
37
class Solution {
    fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        val sortedNums = nums.sorted()
        for (k in 0 until sortedNums.size) {
            if (k > 0 && sortedNums[k] == sortedNums[k - 1]) {
                continue
            }
            for (i in k + 1 until sortedNums.size) {
                if (i > k + 1 && sortedNums[i] == sortedNums[i - 1]) {
                    continue
                }
                var left = i + 1
                var right = sortedNums.size - 1
                while (left < right) {
                    val sum = sortedNums[k].toLong() + sortedNums[i].toLong() + sortedNums[left].toLong() + sortedNums[right].toLong()
                    when {
                        sum < target -> left++
                        sum > target -> right--
                        else -> {
                            result.add(listOf(sortedNums[k], 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--
                        }
                    }
                }
            }
        }
        return result
    }
}

结果

执行用时 : 336 ms, 击败 11.11% 使用 Kotlin 的用户

内存消耗 : 41.36 MB, 击败 11.11% 使用 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
  List<List<int>> fourSum(List<int> nums, int target) {
    List<List<int>> result = [];
    if (nums == null || nums.length < 4) {
      return result;
    }
    nums.sort();
    for (int i = 0; i < nums.length - 3; i++) {
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
      }
      for (int j = i + 1; j < nums.length - 2; j++) {
        if (j > i + 1 && nums[j] == nums[j - 1]) {
          continue;
        }
        int left = j + 1;
        int right = nums.length - 1;
        while (left < right) {
          int sum = nums[i] + nums[j] + nums[left] + nums[right];
          if (sum == target) {
            result.add([nums[i], nums[j], nums[left], nums[right]]);
            while (left < right && nums[left] == nums[left + 1]) {
              left++;
            }
            left++;
            while (left < right && nums[right] == nums[right - 1]) {
              right--;
            }
            right--;
          } else if (sum < target) {
            left++;
          } else {
            right--;
          }
        }
      }
    }
    return result;
  }
}

结果

执行用时 : 448 ms, 击败 -% 使用 Dart 的用户

内存消耗 : 153.90 MB, 击败 100.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
31
32
33
34
35
36
37
func fourSum(nums []int, target int) [][]int {
    var result [][]int
    if len(nums) < 4 {
        return result
    }
    sort.Ints(nums)
    for i := 0; i < len(nums)-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        for j := i + 1; j < len(nums)-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            left, right := j+1, len(nums)-1
            for left < right {
                sum := nums[i] + nums[j] + nums[left] + nums[right]
                if sum == target {
                    result = append(result, []int{nums[i], nums[j], nums[left], nums[right]})
                    for left < right && nums[left] == nums[left+1] {
                        left++
                    }
                    left++
                    for left < right && nums[right] == nums[right-1] {
                        right--
                    }
                    right--
                } else if sum < target {
                    left++
                } else {
                    right--
                }
            }
        }
    }
    return result
}

结果

执行用时 : 12 ms, 击败 45.41% 使用 Go 的用户

内存消耗 : 2.56 MB, 击败 96.90% 使用 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
29
30
31
32
33
34
35
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[][]}
def four_sum(nums, target)
    result = []
    return result if nums.length < 4
    nums.sort!
    (0...nums.length-3).each do |i|
        next if i > 0 && nums[i] == nums[i - 1]
        (i+1...nums.length-2).each do |j|
            next if j > i + 1 && nums[j] == nums[j - 1]
            left = j + 1
            right = nums.length - 1
            while left < right
                sum = nums[i] + nums[j] + nums[left] + nums[right]
                if sum == target
                    result.push([nums[i], nums[j], nums[left], nums[right]])
                    while left < right && nums[left] == nums[left + 1]
                        left += 1
                    end
                    left += 1
                    while left < right && nums[right] == nums[right - 1]
                        right -= 1
                    end
                    right -= 1
                elsif sum < target
                    left += 1
                else
                    right -= 1
                end
            end
        end
    end
    return result
end

结果

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

内存消耗 : 206.90 MB, 击败 20.00% 使用 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
29
30
31
32
33
34
35
36
37
38
39
40
object Solution {
  def fourSum(nums: Array[Int], target: Int): List[List[Int]] = {
    var result: List[List[Int]] = List()
    if (nums.length < 4) {
      return result
    }
    val sortedNums = nums.sorted
    for (i <- 0 until sortedNums.length - 3) {
      if (i > 0 && sortedNums(i) == sortedNums(i - 1)) {
        ()
      } else {
        for (j <- i + 1 until sortedNums.length - 2) {
          if (j > i + 1 && sortedNums(j) == sortedNums(j - 1)) {
            ()
          } else {
            var left = j + 1
            var right = sortedNums.length - 1
            while (left < right) {
              val sum = sortedNums(i).toLong + sortedNums(j).toLong + sortedNums(left).toLong + sortedNums(right).toLong
              if (sum == target) {
                result = result :+ List(sortedNums(i), sortedNums(j), sortedNums(left), sortedNums(right))
                do {
                  left += 1
                } while (left < right && sortedNums(left) == sortedNums(left - 1))
                do {
                  right -= 1
                } while (left < right && sortedNums(right) == sortedNums(right + 1))
              } else if (sum < target) {
                left += 1
              } else {
                right -= 1
              }
            }
          }
        }
      }
    }
    result
  }
}

结果

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

内存消耗 : 55.20 MB, 击败 100.00% 使用 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
34
35
36
37
38
39
40
41
impl Solution {
    pub fn four_sum(nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        if nums.len() < 4 {
            return result;
        }
        let mut sorted_nums = nums;
        sorted_nums.sort();
        for i in 0..sorted_nums.len() - 3 {
            if i > 0 && sorted_nums[i] == sorted_nums[i - 1] {
                continue;
            }
            for j in i + 1..sorted_nums.len() - 2 {
                if j > i + 1 && sorted_nums[j] == sorted_nums[j - 1] {
                    continue;
                }
                let mut left = j + 1;
                let mut right = sorted_nums.len() - 1;
                while left < right {
                    let sum = sorted_nums[i] as i64 + sorted_nums[j] as i64 + sorted_nums[left] as i64 + sorted_nums[right] as i64;
                    if sum == target as i64 {
                        result.push(vec![sorted_nums[i], sorted_nums[j], sorted_nums[left], sorted_nums[right]]);
                        while left < right && sorted_nums[left] == sorted_nums[left + 1] {
                            left += 1;
                        }
                        left += 1;
                        while left < right && sorted_nums[right] == sorted_nums[right - 1] {
                            right -= 1;
                        }
                        right -= 1;
                    } else if sum < target as i64 {
                        left += 1;
                    } else {
                        right -= 1;
                    }
                }
            }
        }
        result
    }
}

结果

执行用时 : 8 ms, 击败 67.74% 使用 Rust 的用户

内存消耗 : 2.17 MB, 击败 32.26% 使用 Rust 的用户

Racket

暂时未解决

1

结果

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

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

Erlang

暂时未解决

1

结果

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

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

Elixir

暂时未解决

1

结果

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

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