Leaky Cauldron
0%

最接近的三数之和

Posted on Edited on

题目(LeetCode #16)

给定一个包括 n 个整数的数组 nums 和 一个目标值 target 。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

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

输出： 2

解释： 与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

  • 3 <= nums.length <= 10³
  • -10³ <= nums[i] <= 10³
  • -104> <= target <= 104

题解

本题与三数之和类似 ，可采用双指针法，差别在于本题可以有重复元素。

由于处理过程中数组已经过排序，故在遍历数组元素的过程中，若 nums[i] + nums[L] + nums[R] > target ，需将 R 左移，以减小三数和，进而减小其与 target 的差值；若 nums[i] + nums[L] + nums[R] < target ，需将 L 右移，增大三数和来达到相同目的。

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
import java.util.Arrays;

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int n = nums.length;
        if (n == 3) return nums[0] + nums[1] + nums[2];

        Arrays.sort(nums);
        int result = 0;
        int minDiff = Integer.MAX_VALUE;


        for (int i = 0; i < n - 2; i++) {
            int l = i + 1, r = n - 1;

            while (l < r) {
                int curSum = nums[i] + nums[l] + nums[r];

                if (curSum == target) return curSum;
                else if (curSum > target) r--;
                else l++;

                int curDiff = Math.abs(curSum - target);
                if (curDiff < minDiff) {
                    minDiff = curDiff;
                    result = curSum;
                }
            }
        }

        return result;
    }
}

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:
    def threeSumClosest(self, nums: list, target: int) -> int:
        list_len = len(nums)
        if not nums or list_len < 3: return 0

        nums.sort()
        min_diff = float('inf')
        result = 0

        for i in range(list_len):
            l = i + 1
            r = list_len - 1
            while l < r:
                cur_sum = nums[i] + nums[l] + nums[r]
                if cur_sum == target: return cur_sum
                cur_diff = abs(cur_sum - target)
                if cur_diff < min_diff:
                    result = cur_sum
                    min_diff = cur_diff

                if cur_sum > target: r -= 1
                else: l += 1

        return result

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
38
39
40
package main

import (
    "math"
    "sort"
)

func threeSumClosest(nums []int, target int) int {
    arrLen := len(nums)
    if nums == nil || arrLen < 3 {
        return 0
    }

    sort.Ints(nums)
    result, curSum, curDiff := 0, 0, 0
    minDiff := math.MaxInt32

    for i, v := range nums {
        L, R := i+1, arrLen-1
        for L < R {
            curSum = v + nums[L] + nums[R]
            if curSum == target {
                return curSum
            }
            curDiff = int(math.Abs(float64(curSum - target)))
            if curDiff < minDiff {
                result = curSum
                minDiff = curDiff
            }

            if curSum > target {
                R--
            } else {
                L++
            }
        }
    }

    return result
}