[record of question brushing] 16. The sum of the nearest three numbers

One 、 Title Description

source ：

Power button （LeetCode）

Give you a length of  n  Array of integers for  nums  and   A target value  target. Please start from  nums  Choose three integers , Make their sum with  target  Nearest .

Returns the sum of the three numbers .

It is assumed that there is only exactly one solution for each set of inputs .

Example  1：

Input ：nums = [-1,2,1,-4], target = 1
Output ：2
explain ： And  target  The closest and  2 (-1 + 2 + 1 = 2) .


Example  2：

Input ：nums = [0,0,0], target = 1
Output ：0


Tips ：

• 3 <= nums.length <= 1000

• -1000 <= nums[i] <= 1000

• -104 <= target <= 104

Two 、 Thought analysis

Sort  +  Double pointer

This question is actually the last question  

【 Record of writing questions 】15. Sum of three numbers

  A deformation of , The purpose of the last topic is to find  

sum == 0

  And this question is   find  

sum == target

  Or closest to

target

Of , On the basis of the previous topic

• according to  sum = L + nums[i] + R  Result , Judge  sum  And target  target  Distance of , Update results if closer  res

• Judge  sum  And  target  The size relationship of , Because the array is ordered , If  sum > target  be  R--, If  sum < target  be  L++, If  sum == target  The distance is  0  Direct return

3、 ... and 、 Code implementation

class Solution {
 public int threeSumClosest(int[] nums, int target) {
 Arrays.sort(nums);
 // Initialize a res
 int res = nums[0] + nums[1] + nums[2];
 for (int i = 0; i < nums.length; i++) {
 // duplicate removal
 if (i > 0 && nums[i] == nums[i - 1]) continue;
 int R = i + 1, L = nums.length - 1;
 while (R < L) {
 int sum = nums[R] + nums[L] + nums[i];
 if (Math.abs(target - sum) < Math.abs(target - res))
 res = sum;
 if (sum > target)
 L--;
 else if (sum < target)
 R++;
 else
 return res;
 }
 }
 return res;
 }
}


Complexity analysis

Time complexity ：

, among  

n

  It's an array  nums  The length of . First of all, we need  

  Time to sort the array , Then in the process of enumeration , Use one cycle  O(n) ： Traversal array , Double pointer  O(n)： enumeration  

L

  and  

R

, So it's a total of  

Spatial complexity ：

 . Sorting requires the use of  

  Space , At the request of the topic   We just store the sorted array , This is the case

 

n

  Is array length

Running results

summary

This question is actually a variation of the previous one , As long as you understand the idea of the last topic , This topic is relatively simple .