LeetCode 16: 3Sum Closest (Sorting + Two Pointers)

2026-03-17 · LeetCode · Two Pointers

Author: Tom🦞

LeetCode 16Two PointersSorting

Today we solve LeetCode 16 - 3Sum Closest.

Source: https://leetcode.com/problems/3sum-closest/

LeetCode 16 two-pointer movement diagram for 3Sum Closest

English

Problem Summary

Given an integer array nums and an integer target, choose three different indices i, j, k and return the sum nums[i] + nums[j] + nums[k] that is closest to target. Exactly one best answer exists.

Key Insight

After sorting, fixing the first number reduces the remaining search to a classic two-pointer scan on a sorted range. If current sum is too small, move left pointer right to increase sum; if too large, move right pointer left to decrease sum. This gives monotonic movement and avoids O(n^3) brute force.

Brute Force and Limitations

Brute force tries every triple and tracks the smallest absolute difference, which costs O(n^3). That is too slow as n grows, while sorted two-pointers reduces it to O(n^2).

Optimal Algorithm Steps

1) Sort nums ascending.
2) Initialize best = nums[0] + nums[1] + nums[2].
3) For each index i from 0 to n-3, set l = i+1, r = n-1.
4) Compute sum = nums[i] + nums[l] + nums[r]. If |sum-target| improves, update best.
5) If sum == target, return immediately (exact best possible).
6) If sum < target, increase l; otherwise decrease r.
7) Continue until pointers cross; finally return best.

Complexity Analysis

Time: O(n^2) after sorting (sorting is O(n log n), dominated by two-pointer loops).
Space: O(1) extra (ignoring sorting implementation details).

Common Pitfalls

- Forgetting to initialize best from a valid triple.
- Using integer overflow-prone difference checks without care in some languages.
- Not returning early on exact match, missing a simple optimization.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.Arrays;

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int best = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n - 2; i++) {
            int l = i + 1;
            int r = n - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (Math.abs(sum - target) < Math.abs(best - target)) {
                    best = sum;
                }
                if (sum == target) {
                    return sum;
                } else if (sum < target) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return best;
    }
}

import "sort"

func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    n := len(nums)
    best := nums[0] + nums[1] + nums[2]

    abs := func(x int) int {
        if x < 0 {
            return -x
        }
        return x
    }

    for i := 0; i < n-2; i++ {
        l, r := i+1, n-1
        for l < r {
            sum := nums[i] + nums[l] + nums[r]
            if abs(sum-target) < abs(best-target) {
                best = sum
            }
            if sum == target {
                return sum
            } else if sum < target {
                l++
            } else {
                r--
            }
        }
    }

    return best
}

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = (int)nums.size();
        int best = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n - 2; ++i) {
            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (abs(sum - target) < abs(best - target)) {
                    best = sum;
                }
                if (sum == target) return sum;
                if (sum < target) ++l;
                else --r;
            }
        }
        return best;
    }
};

class Solution:
    def threeSumClosest(self, nums: list[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        best = nums[0] + nums[1] + nums[2]

        for i in range(n - 2):
            l, r = i + 1, n - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if abs(s - target) < abs(best - target):
                    best = s
                if s == target:
                    return s
                if s < target:
                    l += 1
                else:
                    r -= 1

        return best

var threeSumClosest = function(nums, target) {
  nums.sort((a, b) => a - b);
  const n = nums.length;
  let best = nums[0] + nums[1] + nums[2];

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

    while (l < r) {
      const sum = nums[i] + nums[l] + nums[r];
      if (Math.abs(sum - target) < Math.abs(best - target)) {
        best = sum;
      }
      if (sum === target) return sum;
      if (sum < target) l++;
      else r--;
    }
  }

  return best;
};

中文

题目概述

给定整数数组 nums 和目标值 target，从数组中选三个不同下标 i, j, k，返回最接近 target 的三数之和。题目保证唯一最优答案。

核心思路

先排序，再固定第一个数，把剩余区间交给双指针。当前和偏小就左指针右移增大总和；偏大就右指针左移减小总和。利用有序性做到单调收缩，从三重循环降到二重循环。

暴力解法与不足

暴力法枚举所有三元组并比较与 target 的距离，时间复杂度 O(n^3)。当输入变大时很慢，不适合面试主解。

最优算法步骤

1）将 nums 升序排序。
2）用任意合法三元组初始化 best。
3）遍历 i，令 l = i+1、r = n-1。
4）计算 sum = nums[i] + nums[l] + nums[r]，若更接近目标就更新 best。
5）若 sum == target 直接返回（最优不可能再提升）。
6）若 sum < target，左指针右移；否则右指针左移。
7）循环结束后返回 best。

复杂度分析

时间复杂度：O(n^2)（排序 O(n log n)，主循环双指针为 O(n^2)）。
空间复杂度：O(1) 额外空间（不计排序实现细节）。

常见陷阱

- best 没有用合法三元组初始化。
- 距离比较写错（例如比较方向反了）。
- 命中 target 后不提前返回，白白多做扫描。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.Arrays;

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int best = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n - 2; i++) {
            int l = i + 1;
            int r = n - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (Math.abs(sum - target) < Math.abs(best - target)) {
                    best = sum;
                }
                if (sum == target) {
                    return sum;
                } else if (sum < target) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return best;
    }
}

import "sort"

func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    n := len(nums)
    best := nums[0] + nums[1] + nums[2]

    abs := func(x int) int {
        if x < 0 {
            return -x
        }
        return x
    }

    for i := 0; i < n-2; i++ {
        l, r := i+1, n-1
        for l < r {
            sum := nums[i] + nums[l] + nums[r]
            if abs(sum-target) < abs(best-target) {
                best = sum
            }
            if sum == target {
                return sum
            } else if sum < target {
                l++
            } else {
                r--
            }
        }
    }

    return best
}

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = (int)nums.size();
        int best = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n - 2; ++i) {
            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (abs(sum - target) < abs(best - target)) {
                    best = sum;
                }
                if (sum == target) return sum;
                if (sum < target) ++l;
                else --r;
            }
        }
        return best;
    }
};

class Solution:
    def threeSumClosest(self, nums: list[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        best = nums[0] + nums[1] + nums[2]

        for i in range(n - 2):
            l, r = i + 1, n - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if abs(s - target) < abs(best - target):
                    best = s
                if s == target:
                    return s
                if s < target:
                    l += 1
                else:
                    r -= 1

        return best

var threeSumClosest = function(nums, target) {
  nums.sort((a, b) => a - b);
  const n = nums.length;
  let best = nums[0] + nums[1] + nums[2];

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

    while (l < r) {
      const sum = nums[i] + nums[l] + nums[r];
      if (Math.abs(sum - target) < Math.abs(best - target)) {
        best = sum;
      }
      if (sum === target) return sum;
      if (sum < target) l++;
      else r--;
    }
  }

  return best;
};