力扣00016.最接近的三数之和

发表于 分类于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 7 分钟
最接近的三数之和、数组、双指针、排序、中等

题目描述

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

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

提示：

  • $3 <= nums.length <= 1000$
  • $-1000 <= nums[i] <= 1000$
  • $-10^4 <= target <= 10^4$

解决方法

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
class Solution {
public:
    int threeSumClosest(std::vector<int>& nums, int target) {
        int closest_sum = INT_MAX; // 设置初始最接近值为最大整数值
        int min_diff = INT_MAX; // 设置初始最小差值为最大整数值
        std::sort(nums.begin(), nums.end()); // 对数组进行排序
        for (int i = 0; i < nums.size() - 2; ++i) {
            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                int current_sum = nums[i] + nums[left] + nums[right];
                int diff = abs(target - current_sum);
                if (diff < min_diff) {
                    min_diff = diff;
                    closest_sum = current_sum;
                }
                if (current_sum < target) {
                    ++left;
                } else if (current_sum > target) {
                    --right;
                } else {
                    return current_sum;
                }
            }
        }
        return closest_sum;
    }
};

结果

执行用时 : 44 ms, 击败 55.31% 使用 C++ 的用户

内存消耗 : 10.40 MB, 击败 27.05% 使用 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
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int closestSum = Integer.MAX_VALUE;
        int minDiff = Integer.MAX_VALUE;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];
                int diff = Math.abs(target - currentSum);
                if (diff < minDiff) {
                    minDiff = diff;
                    closestSum = currentSum;
                }
                if (currentSum < target) {
                    left++;
                } else if (currentSum > target) {
                    right--;
                } else {
                    return currentSum;
                }
            }
        }
        return closestSum;
    }
}

结果

执行用时 : 12 ms, 击败 77.58% 使用 Java 的用户

内存消耗 : 41.82 MB, 击败 71.00% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def threeSumClosest(self, nums, target):
        nums.sort()
        closest_sum = float('inf')
        for i in range(len(nums) - 2):
            left, right = i + 1, len(nums) - 1
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                if abs(target - current_sum) < abs(target - closest_sum):
                    closest_sum = current_sum
                if current_sum < target:
                    left += 1
                elif current_sum > target:
                    right -= 1
                else:
                    return current_sum
        return closest_sum

结果

执行用时 : 440 ms, 击败 68.17% 使用 Python 的用户

内存消耗 : 12.94 MB, 击败 84.08% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        closest_sum = float('inf')
        for i in range(len(nums) - 2):
            left, right = i + 1, len(nums) - 1
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                if abs(target - current_sum) < abs(target - closest_sum):
                    closest_sum = current_sum
                if current_sum < target:
                    left += 1
                elif current_sum > target:
                    right -= 1
                else:
                    return current_sum
        return closest_sum

结果

执行用时 : 376 ms, 击败 80.23% 使用 Python3 的用户

内存消耗 : 16.85 MB, 击败 14.26% 使用 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
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}
int threeSumClosest(int* nums, int numsSize, int target) {
    qsort(nums, numsSize, sizeof(int), compare);
    int closestSum = INT_MAX;
    int minDiff = INT_MAX;
    for (int i = 0; i < numsSize - 2; i++) {
        int left = i + 1, right = numsSize - 1;
        while (left < right) {
            int currentSum = nums[i] + nums[left] + nums[right];
            int diff = abs(target - currentSum);
            if (diff < minDiff) {
                minDiff = diff;
                closestSum = currentSum;
            }
            if (currentSum < target) {
                left++;
            } else if (currentSum > target) {
                right--;
            } else {
                return currentSum;
            }
        }
    }
    return closestSum;
}

结果

执行用时 : 28 ms, 击败 65.84% 使用 C 的用户

内存消耗 : 6.64 MB, 击败 27.88% 使用 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
public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        Array.Sort(nums);
        int closestSum = int.MaxValue;
        for (int i = 0; i < nums.Length - 2; i++) {
            int left = i + 1, right = nums.Length - 1;
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];
                if (Math.Abs(target - currentSum) < Math.Abs(target - closestSum)) {
                    closestSum = currentSum;
                }
                if (currentSum < target) {
                    left++;
                } else if (currentSum > target) {
                    right--;
                } else {
                    return currentSum;
                }
            }
        }
        return closestSum;
    }
}

结果

执行用时 : 92 ms, 击败 58.71% 使用 C# 的用户

内存消耗 : 41.35 MB, 击败 5.80% 使用 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
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    nums.sort((a, b) => a - b);
    let closestSum = Infinity;
    for (let i = 0; i < nums.length - 2; i++) {
        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            const currentSum = nums[i] + nums[left] + nums[right];
            if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
                closestSum = currentSum;
            }
            if (currentSum < target) {
                left++;
            } else if (currentSum > target) {
                right--;
            } else {
                return currentSum;
            }
        }
    }
    return closestSum;
};

结果

执行用时 : 60 ms, 击败 99.54% 使用 JavaScript 的用户

内存消耗 : 49.55 MB, 击败 5.43% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function threeSumClosest(nums: number[], target: number): number {
    nums.sort((a, b) => a - b);
    let closestSum: number = Infinity;
    for (let i = 0; i < nums.length - 2; i++) {
        let left: number = i + 1, right: number = nums.length - 1;
        while (left < right) {
            const currentSum: number = nums[i] + nums[left] + nums[right];
            if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
                closestSum = currentSum;
            }
            if (currentSum < target) {
                left++;
            } else if (currentSum > target) {
                right--;
            } else {
                return currentSum;
            }
        }
    }
    return closestSum;
}

结果

执行用时 : 76 ms, 击败 88.81% 使用 TypeScript 的用户

内存消耗 : 51.18 MB, 击败 5.59% 使用 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
class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function threeSumClosest($nums, $target) {
        sort($nums);
        $closestSum = PHP_INT_MAX;
        $length = count($nums);
        for ($i = 0; $i < $length - 2; $i++) {
            $left = $i + 1;
            $right = $length - 1;
            while ($left < $right) {
                $currentSum = $nums[$i] + $nums[$left] + $nums[$right];
                if (abs($target - $currentSum) < abs($target - $closestSum)) {
                    $closestSum = $currentSum;
                }
                if ($currentSum < $target) {
                    $left++;
                } elseif ($currentSum > $target) {
                    $right--;
                } else {
                    return $currentSum;
                }
            }
        }
        return $closestSum;
    }
}

结果

执行用时 : 208 ms, 击败 26.67% 使用 PHP 的用户

内存消耗 : 19.53 MB, 击败 6.67%用 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
class Solution {
    func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
        let sorted = nums.sorted()
        var gap = Int.max
        var finalSum = 0
        for i in 0 ..< sorted.count - 2 {
            var left = i + 1
            var right = sorted.count - 1
            while(left < right) {
                let sum = sorted[i] + sorted[left] + sorted[right]
                let tmp = abs(sum - target)
                if(tmp < gap) {
                    gap = tmp
                    finalSum = sum
                }
                if(sum < target) {
                    left += 1
                } else if(sum > target) {
                    right -= 1
                } else {
                    return sum
                }
            }
        }
        return finalSum
    }
}

结果

执行用时 : 36 ms, 击败 61.70% 使用 Swift 的用户

内存消耗 : 15.40 MB, 击败 6.38% 使用 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
class Solution {
    fun threeSumClosest(nums: IntArray, target: Int): Int {
        nums.sort()
        var closestSum = Int.MAX_VALUE
        for (i in 0 until nums.size - 2) {
            var left = i + 1
            var right = nums.size - 1
            while (left < right) {
                val currentSum = nums[i] + nums[left] + nums[right]
                if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
                    closestSum = currentSum
                }
                if (currentSum < target) {
                    left++
                } else if (currentSum > target) {
                    right--
                } else {
                    return currentSum // 如果等于目标值，直接返回
                }
            }
        }
        return closestSum
    }
}

结果

执行用时 : 208 ms, 击败 84.00% 使用 Kotlin 的用户

内存消耗 : 38.36 MB, 击败 40.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
class Solution {
  int threeSumClosest(List<int> nums, int target) {
    nums.sort();
    int closestSum = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < nums.length - 2; i++) {
      int left = i + 1;
      int right = nums.length - 1;
      while (left < right) {
        int currentSum = nums[i] + nums[left] + nums[right];
        if ((target - currentSum).abs() < (target - closestSum).abs()) {
          closestSum = currentSum;
        }
        if (currentSum < target) {
          left++;
        } else if (currentSum > target) {
          right--;
        } else {
          return currentSum;
        }
      }
    }
    return closestSum;
  }
}

结果

执行用时 : 348 ms, 击败 50.00% 使用 Dart 的用户

内存消耗 : 152.27 MB, 击败 50.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
import "sort"
func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    closestSum := nums[0] + nums[1] + nums[2]
    for i := 0; i < len(nums)-2; i++ {
        left := i + 1
        right := len(nums) - 1
        for left < right {
            currentSum := nums[i] + nums[left] + nums[right]
            if abs(target-currentSum) < abs(target-closestSum) {
                closestSum = currentSum
            }
            if currentSum < target {
                left++
            } else if currentSum > target {
                right--
            } else {
                return currentSum
            }
        }
    }
    return closestSum
}
func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

结果

执行用时 : 8 ms, 击败 95.37% 使用 Go 的用户

内存消耗 : 2.74 MB, 击败 97.61% 使用 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
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer}
def three_sum_closest(nums, target)
    nums.sort!
    closest_sum = nums[0] + nums[1] + nums[2]
    (0..nums.size-2).each do |i|
        left = i + 1
        right = nums.size - 1
        while left < right
            current_sum = nums[i] + nums[left] + nums[right]
            if (target - current_sum).abs < (target - closest_sum).abs
                closest_sum = current_sum
            end
            if current_sum < target
                left += 1
            elsif current_sum > target
                right -= 1
            else
                return current_sum
            end
        end
    end
    closest_sum
end

结果

执行用时 : 344 ms, 击败 50.00% 使用 Ruby 的用户

内存消耗 : 206.89 MB, 击败 -% 使用 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
object Solution {
  def threeSumClosest(nums: Array[Int], target: Int): Int = {
    val sorted = nums.sorted
    var closestSum = sorted(0) + sorted(1) + sorted(2)
    for (i <- 0 until sorted.length - 2) {
      var left = i + 1
      var right = sorted.length - 1
      while (left < right) {
        val currentSum = sorted(i) + sorted(left) + sorted(right)
        if (math.abs(target - currentSum) < math.abs(target - closestSum)) {
          closestSum = currentSum
        }
        if (currentSum < target) {
          left += 1
        } else if (currentSum > target) {
          right -= 1
        } else {
          return currentSum
        }
      }
    }
    closestSum
  }
}

结果

执行用时 : 548 ms, 击败 -% 使用 Scala 的用户

内存消耗 : 54.30 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
impl Solution {
    pub fn three_sum_closest(nums: Vec<i32>, target: i32) -> i32 {
        let mut sorted = nums;
        sorted.sort();
        let mut closest_sum = sorted[0] + sorted[1] + sorted[2];
        for i in 0..sorted.len() - 2 {
            let mut left = i + 1;
            let mut right = sorted.len() - 1;
            while left < right {
                let current_sum = sorted[i] + sorted[left] + sorted[right];
                if (target - current_sum).abs() < (target - closest_sum).abs() {
                    closest_sum = current_sum;
                }
                if current_sum < target {
                    left += 1;
                } else if current_sum > target {
                    right -= 1;
                } else {
                    return current_sum;
                }
            }
        }
        closest_sum
    }
}

结果

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

内存消耗 : 2.05 MB, 击败 51.81% 使用 Rust 的用户

Racket

暂时未解决

1

结果

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

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

Erlang

暂时未解决

1

结果

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

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

Elixir

暂时未解决

1

结果

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

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