/**
*
https://leetcode.cn/problems/3sum-closest/description/
16. 最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
*/
// ---------------------------------------------------
/*
这种算法超时了
改进： 使用 排序 + 双指针
*/
var threeSumClosest = function (nums, target) {
nums.sort((a, b) => a - b);
let minDiff = Number.MAX_SAFE_INTEGER;
let sum = 0;
for (let i = 0; i < nums.length; i++) {
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
let newSum = nums[i] + nums[left] + nums[right];
let newDiff = Math.abs(newSum - target);
if (newDiff < minDiff) {
sum = newSum;
minDiff = newDiff;
}
if (newSum > target) {
right--;
} else {
left++;
}
}
}
return sum;
};
console.log(threeSumClosest([0, 1, 2], 3)); // 3
console.log(threeSumClosest([-1, 2, 1, -4], 1)); // 2
console.log(threeSumClosest([0, 0, 0], 1)); // 0
console.log(threeSumClosest([1, 1, 1, 0], -100)); // 2
console.log(threeSumClosest([4, 0, 5, -5, 3, 3, 0, -4, -5], -2)); // -2
console.log(threeSumClosest([-100, -98, -2, -1], -101)); // -101
// console.log(
// threeSumClosest(
// [
// 777, 286, -518, 749, 965, -15, 497, 566, 683, -231, 381, -9, 930, 510,
// -161, -431, 307, -288, -643, -198, 556, -576, 757, -777, -994, -953, -908,
// -890, -92, 561, -333, 905, -881, -387, -247, -326, -654, -116, 213, 577,
// 66, 236, -179, 373, 698, -230, 602, 337, -669, 798, -771, -395, 717, 459,
// 174, -457, -452, 414, -526, 253, -782, 962, -279, -13, 693, 886, 422, 146,
// -906, 932, -818, -710, 30, -405, -347, -964, 621, 678, -1, 835, 68, -623,
// -37, 309, 136, -496, -909, 593, 481, -786, 825, -660, 423, 370, -376, 694,
// 88, 79, 896, 503, -358, -289, 143, 780, -225, 440, -989, 544, 622, 775,
// -810, 229, 574, -218, 961, -736, -806, -950, -907, -143, -998, -3, -944,
// -409, 813, -493, -715, -205, 807, -569, -521, -800, 729, -523, -160, 119,
// 372, -857, 121, 255, -886, -41, -27, 827, -95, 127, 767, -653, 771, -480,
// -776, 446, -276, 506, -889, 458, -80, 953, 746, 797, -735, 625, -933,
// -488, 726, 513, 571, 124, 955, -769, -897, 94, 171, -157, 525, 913, -713,
// 70, -823, 711, 679, 380, 281, -839, 901, -359, 319, -281, -194, 514, 671,
// -261, 861, 974, -490, 467, 328, -427, 368, -228, 764, 2, 182, -234, -841,
// 677, 271, -468, 740, 433, -371, -236, 613, -617, -372, 952, -796, 543,
// 776, -522, -478, -914, 929, -259, -48, -840, -570, -297, -747, -675, 103,
// 461, 387, 34, 67, 724, 118, 539, -323, 138, -820, 290, 230, 737, 730,
// -716, -700, -987, -88, -535, -960, -305, -365, -838, 580, -882, 979, -600,
// 487, 938, -783, -135, 547, 183, -665, -291, 277, 187, -287, 212, 202, 657,
// -193, 700, -726, 603, 246, 651, 304, -741, -590, 209, -528, 233, -828,
// 778, 900, -799, 639, 894, -658, 795, -126, -325, -550, -336, 270, 681,
// -472, -749, -191, 455, -879, 421, -122, 44, -133, -666, 809, -211, 633,
// -602,
// ],
// -7843
// )
// ); // -101
console.log(
threeSumClosest(
[
-314, 975, -143, 23, 897, 714, 956, 654, 690, -345, -989, -979, -826,
-299, -408, 933, 588, -619, -491, -99, -353, -182, 411, 978, -261, -271,
-983, -60, -874, 11, 253, -198, 977, 99, 371, -884, 14, -482, -757, 251,
869, 587, -706, -885, -220, -472, 738, 996, 22, 923, 407, 926, -759, 851,
-124, 513, -142, 60, 268, -944, 612, 890, 192, 964, 34, -368, 910, 651,
18, 152, -239, 900, 991, 646, 559, -668, 246, 256, 111, 375, 195, 197,
-935, -457, -371, -251, 968, 162, 515, 473, 438, -349, -347, -116, -31,
-579, 145, 183, -602, -128, 421, -815, -824, 650, -170, 285, 708, -268,
-105, 166, -914, 325, 368, -429, 405, -42, 349, -570, 228, -702, -875,
773, -304, -865, -323, -215, 364, -910, 671, -937, -356, 734, -844, -506,
682, 46, 648, 76, 477, -996, -419, 603, -134, -504, 328, 331, 494, -293,
-978, 931, -68, 401, -37, 3, -410, -362, 698, 535, 135, 279, 959, -65,
-374, -916, -375, -746, -565, 642, 378, 275, 21, -597, 259, -62, -463,
-434, -707, -49, -859, 462, 394, -227, 70, 239, -450, 707, -36, -762,
-540, 985, 417, 821, -69, -561, 63, 637, -384, -691, -361, 223, -127, 122,
-318, 564, 128, -195, 217, 102, -742, 597, 220, -240, -711, 323, -342,
-138, -678, -648, 954, -918, 153, -77, 388, -854, -804, 873, 823, 557,
-840, 106, -675, -201, -873, 73, -67, -275, 620, -735, -93, -91, 350,
-322, -806, 213, -674, -10, -102, 655, 713, -572, -933, 563, -58, 881,
110, -527, 731, -987, 376, -451, -163, -718, -513, -175, 495, -183, -629,
550, 945, -659, -601, 854, -562, 413, 842, 470, 706, 489, -38, 863, -535,
48, -564, 158, -468, 806, 922, -667, -12, 579, -743, -582, -909, 117, 437,
-763, -174, 683, 131, -233, -587, 62, -259, -319, 294, -237, -591, -770,
-141, -656, 283, -213, -494, -439, -796, 750, -890, -799, -850, 454, -34,
-159, -787, 43, 493, -794, -972, 383,
],
9486
)
); // ？？？
