This is the 10th day of my participation in the First Challenge 2022, for more details: First Challenge 2022

First, write first

I was recently thinking about a question that another reader asked me, “How do you use optimal solutions?” “, indeed this is a very good problem, at that time I was also a mute, prevarication a few words, this problem was I deeply remember, how do I change to find the optimal solution (more optimal solution)? I’m obviously not strong enough on my own. After studying Geek Time’s Algorithmic Interviews 40, I came up with a few ideas:

1. The most important method depends on everyone. Now there are more than 7000 wechat public accounts paying attention to me. I hope readers of this tweet can comment: support your old cousin or what you want to say;

2 their Baidu Google is not wrong, it is more difficult to come up with the optimal solution solely by their heads, so we should learn baidu Google, learn the methods of others, “choose its good from it, not good and change”;

3. Transfer to LeetCode English website. After learning Lecture 40 of Algorithm Interview, the teacher taught LeetCode questions.

I heard you’re still writing a two-layer for loop to solve the sum of two numbers?

LeetCode 2: Sum of two numbers transfer gate: the median of two sorted arrays, “most” technical solution!

LeetCode 第 3 题 : Longest loop transport gate: Horse-and-cart algorithm to solve longest loop! Manacher

LeetCode 4 题 conversion of string to integer (ATOI) : Solve ATOI with “foolish old man removing mountains” method, think clever!

Continue solving LeetCode, the longest public prefix

One of LeetCode’s “most classic” algorithm problems: the sum of three numbers

Question 7: The sum of the nearest three numbers, for the interview, looking forward to your participation.

Today’s topic

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.

Example:

For example, given the array nums = [-1.2.1, -4], and target =1.The sum of the three numbers closest to target is2. (-1 + 2 + 1 = 2).
Copy the code

Three, the analysis

A layer of for loop followed by a layer of while loop:

Fourth, the problem solving

  • My approach:

For +while time complexity: O(n^2)

class Solution(object) :
	def threeSumClosest(self, nums, target) :
		""" :type nums: List[int] :type target: int :rtype: int """
		# distance
		distance_t = 10000
		# return result
		result_sum = 0
		# 1. Sort for easy comparison
		nums.sort()
		# Layer 1: Find your head
		for i in range(len(nums)-2):
			left = i + 1
			right = len(nums) - 1
			first = nums[i]
			# Layer 2: Flanking left and right
			while left < right:
				second = nums[left]
				third = nums[right]
				sum = first + second + third
				abs_flag = abs(sum - target)
				if abs_flag == 0: # the closest
					return target
				elif abs_flag < distance_t: Record the current sum and distance_t
					result_sum = sum
					distance_t = abs_flag
				if sum > target:
					right -= 1   # Left shift increased
				else:
					left += 1    # Right shift becomes smaller
		return result_sum
Copy the code
  • Submit the results

Test data: 125 groups running time: 68ms beat percentage :79.62%

As you can see from the above results, this lookup method should be a common one, with the submission results clustered in this area.

In order to find a better method, I searched the English official website of LeetCode, and found that in addition to my method, there are mainly the following two methods:

  1. Sort + double pointer (same as my method, submit result is not as good as list traversal directly)

  2. Enumeration + classification comparison (mainly to introduce you to learn this method)

Here is a good introduction to Daniel’s method:

  • Daniel method

  • Thinking analytical

  • code
class Solution(object) :
	def threeSumClosest(self, nums, target) :
		""" :type nums: List[int] :type target: int :rtype: int """
		nums.sort()
		length = len(nums)
		closest = []
		
		for i, num in enumerate(nums[0: -2]):
			l, r = i + 1, length - 1
			
			# different with others' solution
			
			if num + nums[r] + nums[r - 1] < target: # the biggest
				closest.append(num + nums[r] + nums[r - 1])
			elif num + nums[l] + nums[l + 1] > target: # minimum
				closest.append(num + nums[l] + nums[l + 1])
			else:
				while l < r:  # Left/right mix
					closest.append(num + nums[l] + nums[r])
					if num + nums[l] + nums[r] < target:  # small, move to the right
						l += 1
					elif num + nums[l] + nums[r] > target: # large, move to the left
						r -= 1
					else:  # is equal
						return target
		Sort by distance from target from smallest to largest
		closest.sort(key=lambda x: abs(x - target))
		return closest[0]
Copy the code
  • Submit the results

Test data: 125 groups running time: 28ms beat percentage :99.09%

Five, doubt

Data structure is still very profound, selection, design, are to learn, including the idea of algorithm, logical choice, I hope a month, two months, more and more, I can be more proficient.

Six, the concluding

Persistence and hard work: results.

Like to see the message forwarding, four support, the original is not easy. Ok, see you next time, I love the cat love technology, more love si si’s old cousin Da Mian ଘ(˙꒳˙)ଓ Di Di