16. Сумма ближайших трех чисел

LeetCode

Дан массив nums из n целых чисел и целевое значение target. Найдите три целых числа в nums, сумма которых ближе всего к цели. Возвращает сумму этих трех чисел. Предполагается, что для каждого набора входных данных существует только уникальный ответ.

示例：

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

решение

решение этой проблемы и15. Сумма трех чиселпохожи, просто сравнивая объекты из0сталtarget. Это также практика сортировки + двойные указатели.

  • еслиa+b+c ≥ target, тоcСоответствующий указатель перемещается на одну позицию влево
  • еслиa+b+c < target, тоbСоответствующий указатель перемещается на одну позицию вправо
def threeSumClosest(nums, target):

    nums.sort()
    n = len(nums)
    best = 10**7

    # 根据差值的绝对值来更新答案
    def update(cur):
        nonlocal best
        if abs(cur - target) < abs(best - target):
            best = cur
    # 枚举a
    for i in range(n):
        # 保证和上一次枚举的元素不相等
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # 使用双指针枚举b, c
        L, R = i + 1, n - 1
        while L < R:
            sum = nums[i] + nums[L] + nums[R]
            # 如果和为target，那么它就是最接近的和，直接返回
            if sum == target:
                return target
            update(sum)  # 每次指针变化过后，更新答案
            if sum < target:
                # 如果和小于target，b 对应的指针向右移动一位
                L0 = L + 1
                # 移动到下一个不相等的元素
                while L0 < R and nums[L0] == nums[L]:
                    L0 += 1
                L = L0
            else:
                # 如果和大于target，c 对应的指针向左移动一位
                R0 = R - 1
                # 移动到下一个不相等的元素
                while L < R0 and nums[R0] == nums[R]:
                    R0 -= 1
                R = R0
                
    return best
Анализ сложности
  • Временная сложность: O(N^2), где N — длина массива nums. Сначала нам нужно O(NlogN) времени для сортировки массива, затем в процессе перечисления мы используем цикл O(N) для перечисления a и двойной указатель O(N) для перечисления b и c, так что общее количество равно O ( N ^ 2).
  • Пространственная сложность: O(logN). Для сортировки требуется пространство O(logN). Однако мы модифицировали входной массив nums, что не обязательно разрешено в реальной ситуации, поэтому его также можно рассматривать как использование дополнительного массива для хранения копии nums и ее сортировки.На данный момент сложность пространства составляет O (Н).

Официальный ответ Ликоу

Категории