16. 最接近的三数之和
代码
javascript
// 16. 最接近的三数之和:https://leetcode.cn/problems/3sum-closest/description/
// 输入:nums = [-1,2,1,-4], target = 1
// 输出:2
export function threeSumClosest (nums, target) {
nums = nums.sort((a, b) => a - b)
const len = nums.length
let res = 0
let diffNum = Number.MAX_SAFE_INTEGER
for (let i = 0; i < len - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) {
continue
}
let sum = nums[i] + nums[i + 1] + nums[i + 2]
if (sum > target) {
if (sum - target < diffNum) {
res = sum
}
break
}
sum = nums[i] + nums[len - 2] + nums[len - 1]
if (sum < target) {
if (target - sum < diffNum) {
diffNum = target - sum
res = sum
}
continue
}
let j = i + 1
let k = len - 1
while (j < k) {
sum = nums[i] + nums[j] + nums[k]
if (sum === target) return target
if (sum > target) {
if (sum - target < diffNum) {
diffNum = sum - target
res = sum
}
k--
} else {
if (target - sum < diffNum) {
diffNum = target - sum
res = sum
}
j++
}
}
}
return res
}
typescript
// 16. 最接近的三数之和:https://leetcode.cn/problems/3sum-closest/description/
// 输入:nums = [-1,2,1,-4], target = 1
// 输出:2
export function threeSumClosest (nums: number[], target: number): number {
nums = nums.sort((a, b) => a - b)
const len = nums.length
let res = 0
let diffNum = Number.MAX_SAFE_INTEGER
for (let i = 0; i < len - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) {
continue
}
let sum = nums[i] + nums[i + 1] + nums[i + 2]
if (sum > target) {
if (sum - target < diffNum) {
res = sum
}
break
}
sum = nums[i] + nums[len - 2] + nums[len - 1]
if (sum < target) {
if (target - sum < diffNum) {
diffNum = target - sum
res = sum
}
continue
}
let j = i + 1
let k = len - 1
while (j < k) {
sum = nums[i] + nums[j] + nums[k]
if (sum === target) return target
if (sum > target) {
if (sum - target < diffNum) {
diffNum = sum - target
res = sum
}
k--
} else {
if (target - sum < diffNum) {
diffNum = target - sum
res = sum
}
j++
}
}
}
return res
}
测试代码
ts
import { expect, test } from 'vitest'
import { threeSumClosest } from './typescript.ts'
import { threeSumClosest as threeSumClosestJs } from './javascript.js'
test('nums = [-1,2,1,-4], target = 1', () => {
expect(threeSumClosest([-1,2,1,-4], 1)).toBe(2)
})
test('nums = [-1,2,1,-4], target = 1', () => {
expect(threeSumClosestJs([-1,2,1,-4], 1)).toBe(2)
})
test('nums = [-1,2,1,1,-4], target = 1', () => {
expect(threeSumClosest([-1,2,1,1,-4], 1)).toBe(1)
})
test('nums = [-1,2,1,1,-4], target = 1', () => {
expect(threeSumClosestJs([-1,2,1,1,-4], 1)).toBe(1)
})
test('nums = [-4,-2,-1,-1,1,1,2,1,-4,4], target = 1', () => {
expect(threeSumClosest([-4,-2,-1,-1,1,1,2,1,-4,4], 1)).toBe(1)
})
test('nums = [-4,-2,-1,-1,1,1,2,1,-4,4], target = 1', () => {
expect(threeSumClosestJs([-4,-2,-1,-1,1,1,2,1,-4,4], 1)).toBe(1)
})