Shulou(Shulou.com)06/01 Report--

This article is about how to solve the problem of the sum of three numbers in leetcode. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Topic link

Https://leetcode-cn.com/problems/3sum-closest/

Topic description

Given an array of n integers nums and a target value target. Find 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 a unique answer for each set of inputs.

For example, a given array nums = [- 1, 2, and target = 1].

The sum of the three numbers closest to target is 2. (- 1 + 2 + 1 = 2). The idea of solving the problem

Tags: sorting and double pointers

Because this topic needs to calculate three numbers, if we rely on violent enumeration, the time complexity will reach O (n ^ 3), so we need to reduce the time complexity.

First, the array is sorted with time complexity O (nlogn).

In the array nums, iterate through one value each time, using its subscript I to form a fixed value nums [I]

Then use the front pointer to point to start = I + 1 and the back pointer to point to end = nums.length-1, that is, at the end

According to the result of sum = nums [I] + nums [start] + nums [end], judge the distance between sum and target target, and update the result ans if it is closer.

At the same time, judge the size relationship between sum and target, because the array is ordered, if sum > target, then end--, if sum

< target 则 start++，如果sum == target 则说明距离为0直接返回结果 整个遍历过程，固定值为n次，双指针为n次，时间复杂度为O(n^2) 总时间复杂度：O(nlogn) + O(n^2) = O(n^2) 代码class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int ans = nums[0] + nums[1] + nums[2]; for(int i=0;i target) end--; else if(sum < target) start++; else return ans; } } return ans; }}画解

Thank you for reading! This is the end of this article on "how to solve the problem of the sum of three numbers in leetcode". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it for more people to see!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.