3Sum Closest Problem


Description

LeetCode Problem 16.

Given an integer array nums of length n 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:

1
2
3
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).

Example 2:

1
2
Input: nums = [0,0,0], target = 1
Output: 0

Constraints:

  • 3 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • -10^4 <= target <= 10^4


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < n-2; ++i) {
            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum3 = nums[i] + nums[l] + nums[r];
                if (abs(ans - target) > abs(sum3 - target)) // Update better ans
                    ans = sum3;
                if (sum3 == target) break;
                if (sum3 > target)
                    // Sum3 is greater than the target, to minimize the difference, we have to decrease our sum3
                    --r; 
                else
                    // Sum3 is lesser than the target, to minimize the difference, we have to increase our sum3
                    ++l; 
            }
        }
        return ans;
    }
};




Related Posts

Sum Of Subsequence Widths Problem

LeetCode 891. The width of a sequence is the difference...

Sort An Array Problem

LeetCode 912. Given an array of integers nums, sort the...

Reordered Power Of 2 Problem

LeetCode 869. You are given an integer n. We reorder...

Reorder Data In Log Files Problem

LeetCode 937. You are given an array of logs. Each...

Minimum Increment To Make Array Unique Problem

LeetCode 945. You are given an integer array nums. In...

Largest Number At Least Twice Of Others Problem

LeetCode 747. You are given an integer array nums where...