Topic describes

Given an array of n integers nums and a target value target. Identify the three integers in NUMs so that their sum is closest to target. Returns the sum of these three numbers. Assume that there is only one answer for each set of inputs.

The sample

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

3 <= nums.length <= 10^ 3-10 ^3 <= nums[I] <= 10^ 3-10 ^4 <= target <= 10^4

Source: LeetCode link: leetcode-cn.com/problems/3s…

Analysis of the

The closest the sum of the three numbers to the target is the sum of a,b, and c as a+b+c-t approaches 0.

  1. The topic is similar to 15. The sum of three numbers, which can be solved by some modifications according to the idea of the sum of three numbers.
  2. The sum of three numbers is the combination of a+b+ C =0. Here is the sum of a+b+ C closer to target. We traverse the array according to the method of traversal number group in the sum of three numbers, and then judge within the loop body whether the sum of the current three numbers is closer to target.

Example: nums = {-1,2,1,-4}

  1. First sort the array
  2. Loop through the array to get a
  3. Double pointer left,right to a+1 and numssize-1 respectively
  4. Determine whether the absolute value of the difference between the sum of the current three numbers and target is smaller than the absolute value of the difference between the sum of the three numbers obtained in previous cycles (the smaller the absolute value of the difference is, the closer it is to target).
  5. When a+b+ C >target, b+ C is slightly larger and the right pointer moves to the left because the array is sorted
  6. When a+b+c
  7. If a+b+c=target, the result is the sum of a+b+ C
  8. Return the sum of three numbers whose differences are closer to 0

implementation

int compare(const void *a, const void *b)
{
    return* (int*)a - *(int*)b;
}

int threeSumClosest(int* nums, int numsSize, int target)
{
    if (numsSize < 3) {
        return NULL;
    }
    qsort(nums, numsSize, sizeof(nums[0]), compare);
    int sum = nums[0] + nums[1] + nums[numsSize- 1];  // The sum of the three numbers closest to target, the smaller the absolute value of the difference, the closer to target
    for (int i = 0; i < numsSize; i++) {
        int left = i + 1;
        int right = numsSize - 1;
        while (left < right) {
            int tmpSum = nums[i] + nums[left] + nums[right];
            if (abs(tmpSum - target) < abs(sum - target)) {
                sum = tmpSum;
            }
            if (tmpSum > target) {
                right--;
            } else if (tmpSum < target) {
                left++;
            } else {
                returnsum; }}}return sum;
}
Copy the code