leetcode-16 最接近的三数和

[ronghaoZHI]

leetcode 16

最接近的三数和 [-1, 2, 1, 4] target = 1;
output =2; (-1 + 2 + 1 = 2)

解题思路

1. 暴力求解 复杂度 O(n 三次方)
2. 类似 求三个数和； 排序 + 双指针 复杂度 O(n * log(n)_) + O(n 平方) = O(n 平方)

		function threeSum(nums, target) {
			nums.sort((a, b)=> a-b);
			let ans = nums[0] + nums[1] + nums[2];
			// let res = [nums[0], nums[1], nums[2]];
			for(let i = 0; i < nums.length; i++) {
				let left = i + 1, right = nums.length - 1;
				while(left < right) {
					let sum = nums[i] + nums[left] + nums[right];
					// 比较 差值大小， 更新 ans
					if(Math.abs(target - sum) < Math.abs(target - ans)) {
						// res = [nums[i], nums[left], nums[right]];
						ans = sum;
					}
					// 更新双指针
					if(sum > target) {
						right--;
					} else if(sum < target) {
						left++
					} else {
						return ans;
					}
				}
			}
			return ans;
		}
		console.log(threeSum([-1, 2, 1, 4], 1));