0016. 最接近的三数之和 3Sum Closest

问题描述

双指针法

可以使用双指针法遍历整个数组. 具体的步骤如下:

• 先对整数数组进行排序
• 然后计算特殊情况
  • 整数数组长度为3时, 直接返回前三个元素的和
  • 前三个元素的和等于 target 时, 也可以直接返回
• 遍历数组中所有元素(一直到倒数第三个元素), 作为三个数中的第一个数
  • 对于第二个和第三个数, 我们使用双指针法来遍历
  • 先计算三个元素的和 sum, 以及 sum 与 target 的差值绝对值 diff
  • 如果 sum == target, 直接返回
  • 如果 sum < target, 将双指针的左侧元素向右移一位, left += 1
  • 如果 sum > target, 将双指针的右侧元素向左移一位, right -= 1
  • 如果 diff 比目前最小的差值还小, 那就更新它

代码实现如下:

Rust

#![allow(unused)]
fn main() {
use std::cmp::Ordering;

// 靠拢型双指针
pub fn three_sum_closest2(nums: Vec<i32>, target: i32) -> i32 {
    let len = nums.len();
    assert!(nums.len() >= 3);

    // 对数组排序.
    let mut nums = nums;
    nums.sort();

    // 先处理特别情况.
    let mut closest: i32 = nums[0] + nums[1] + nums[2];
    if len == 3 || closest == target {
        return closest;
    }
    let mut closest_diff: i32 = i32::MAX;

    // 遍历数组.
    for i in 0..(len - 2) {
        // 初始化双指针.
        let mut left = i + 1;
        let mut right = len - 1;
        while left < right {
            // 不需要检查整数溢出.
            let sum = nums[i] + nums[left] + nums[right];
            match sum.cmp(&target) {
                // 如果找到了与 `target` 相同的结果, 就不需要再循环了, 直接返回.
                Ordering::Equal => return sum,
                // 移动指针
                Ordering::Less => left += 1,
                Ordering::Greater => right -= 1,
            }

            let diff = (sum - target).abs();
            if diff < closest_diff {
                // 更新新的最接近值.
                closest = sum;
                closest_diff = diff;
            }
        }
    }

    closest
}
}

C++

#include <cassert>
#include <climits>

#include <algorithm>
#include <vector>

class Solution {
 public:
  static
  int threeSumClosest(std::vector<int>& nums, int target) {
    // 先排序
    std::sort(nums.begin(), nums.end());
    assert(nums.size() >= 3);

    int closest = nums[0] + nums[1] + nums[2];
    int min_diff = INT_MAX;
    if (nums.size() == 3 || closest == target) {
      return closest;
    }

    // 遍历数组
    for (size_t i = 0; i < nums.size() - 2; ++i) {
      // 初始化双指针
      int left = i + 1;
      int right = nums.size() - 1;
      int first = nums[i];

      while (left < right) {
        int sum = first + nums[left] + nums[right];
        // 如果与 target 相等, 就直接返回.
        if (sum == target) {
          return sum;
        } else if (sum < target) {
          left += 1;
        } else if (sum > target) {
          right -= 1;
        }

        const int diff = std::abs(sum - target);
        if (diff < min_diff) {
          // 更新最小差值
          min_diff = diff;
          closest = sum;
        }
      }
    }

    return closest;
  }
};