算法题/双指针：最靠近目标数的三数

题目

给定一个未排序数数组和一个目标数，在数组中找到一个和尽可能接近目标数的三元组，返回该三元组的和。如果这样的三元组不止一个，则返回具有最小和的三元组的和。

示例1：

输入：[-2, 0, 1, 2], target=2
输出：1
解释：[-2, 1, 2]是最靠近2的三元组

示例2：

输入：[-3, -1, 1, 2], target=1
输出：0
解释：[-3, 1, 2]是最靠近1的三元组

解答1：

Java

import java.util.*;

class TripletSumCloseToTarget {

  public static int searchTriplet(int[] arr, int targetSum) {
    if (arr == null || arr.length < 3)
      throw new IllegalArgumentException();

    Arrays.sort(arr);
    int smallestDifference = Integer.MAX_VALUE;
    for (int i = 0; i < arr.length - 2; i++) {
      int left = i + 1, right = arr.length - 1;
      while (left < right) {
        //将三个数字的和与'targetSum'进行比较可能会导致溢出
        //因此，我们试图去找到一个目标差异
        int targetDiff = targetSum - arr[i] - arr[left] - arr[right];
        if (targetDiff == 0) //找到和为targetSum的三元组
          return targetSum - targetDiff; //返回所有元素的和

        // 下面的判定条件的第二部分是为了解决重复三元组的问题，
        //在于targetSum差值相等的情况下，targetDiff>smallestDifference时，
        //三数之和越小（target=targetDiff+三数之和）
        if (Math.abs(targetDiff) < Math.abs(smallestDifference)
            || (Math.abs(targetDiff) == Math.abs(smallestDifference) && targetDiff > smallestDifference))
          smallestDifference = targetDiff; //保存该targetDiff

        if (targetDiff > 0)
          left++; //我们将left指针右移来得到一个更大的数，从而得到更大的currentSum
        else
          right--; //我们将right指针左移来得到一个更小的数，从而得到更小的currentSum
      }
    }
    return targetSum - smallestDifference;
  }

  public static void main(String[] args) {
    System.out.println(TripletSumCloseToTarget.searchTriplet(new int[] { -2, 0, 1, 2 }, 2));
    System.out.println(TripletSumCloseToTarget.searchTriplet(new int[] { -3, -1, 1, 2 }, 1));
    System.out.println(TripletSumCloseToTarget.searchTriplet(new int[] { 1, 0, 1, 1 }, 100));
  }
}

JavaScript

function searchTriplet(arr, targetSum) {
  if (arr === null || arr.length < 3) {
    throw new Error('Invalid input: arr must have at least 3 elements');
  }
  
  arr.sort((a, b) => a - b);
  let smallestDifference = Infinity;
  
  for (let i = 0; i < arr.length - 2; i++) {
    let left = i + 1;
    let right = arr.length - 1;
    
    while (left < right) {
      let targetDiff = targetSum - arr[i] - arr[left] - arr[right];
      
      if (targetDiff === 0) {
        return targetSum - targetDiff;
      }
      
      if (Math.abs(targetDiff) < Math.abs(smallestDifference) ||
          (Math.abs(targetDiff) === Math.abs(smallestDifference) && targetDiff > smallestDifference)) {
        smallestDifference = targetDiff;
      }
      
      if (targetDiff > 0) {
        left++;
      } else {
        right--;
      }
    }
  }
  
  return targetSum - smallestDifference;
}

console.log(searchTriplet([-2, 0, 1, 2], 2));
console.log(searchTriplet([-3, -1, 1, 2], 1));
console.log(searchTriplet([1, 0, 1, 1], 100));

Python

def search_triplet(arr, target_sum):
    if arr is None or len(arr) < 3:
        raise ValueError('Invalid input: arr must have at least 3 elements')

    arr.sort()
    smallest_difference = float('inf')

    for i in range(len(arr) - 2):
        left = i + 1
        right = len(arr) - 1

        while left < right:
            target_diff = target_sum - arr[i] - arr[left] - arr[right]

            if target_diff == 0:
                return target_sum - target_diff

            if abs(target_diff) < abs(smallest_difference) or (abs(target_diff) == abs(smallest_difference) and target_diff > smallest_difference):
                smallest_difference = target_diff

            if target_diff > 0:
                left += 1
            else:
                right -= 1

    return target_sum - smallest_difference


print(search_triplet([-2, 0, 1, 2], 2))
print(search_triplet([-3, -1, 1, 2], 1))
print(search_triplet([1, 0, 1, 1], 100))

Go

package main

import (
	"fmt"
	"math"
	"sort"
)

func searchTriplet(arr []int, targetSum int) int {
	if arr == nil || len(arr) < 3 {
		panic("Invalid input: arr must have at least 3 elements")
	}

	sort.Ints(arr)
	smallestDifference := math.MaxInt32

	for i := 0; i < len(arr)-2; i++ {
		left := i + 1
		right := len(arr) - 1

		for left < right {
			targetDiff := targetSum - arr[i] - arr[left] - arr[right]

			if targetDiff == 0 {
				return targetSum - targetDiff
			}

			if math.Abs(float64(targetDiff)) < math.Abs(float64(smallestDifference)) ||
				(math.Abs(float64(targetDiff)) == math.Abs(float64(smallestDifference)) && targetDiff > smallestDifference) {
				smallestDifference = targetDiff
			}

			if targetDiff > 0 {
				left++
			} else {
				right--
			}
		}
	}

	return targetSum - smallestDifference
}

func main() {
	fmt.Println(searchTriplet([]int{-2, 0, 1, 2}, 2))
	fmt.Println(searchTriplet([]int{-3, -1, 1, 2}, 1))
	fmt.Println(searchTriplet([]int{1, 0, 1, 1}, 100))
}