blog.image

[LeetCode][Medium] 16. 3Sum Cloest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

題目

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

思路

如同 15. 3sum,但這次要記錄最接近的值,如果剛好 hit target 就直接 return

Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    nums.sort((a, b) => a - b)
    let res = nums[0] + nums[1] + nums[2]
    let sum = 0
    let left, right
    
    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue
        left = i + 1
        right = nums.length - 1
        
        while(left < right) {
            sum = nums[i] + nums[left] + nums[right]
            if (sum < target) {
                left++
            } else if (sum > target) {
                right--
            } else {
                return sum
            }
            if (Math.abs(sum - target) < Math.abs(res - target)) res = sum
        }
    }
    return res
};

Complexity

  • Time complexity : O(n^2)
  • Space complexity : O(1)

類似文章

record.image

Engineering

[LeetCode][Medium] 17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

author.image
1 min
record.image

Engineering

[LeetCode][Medium] 15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

author.image
1 min