This is the ninth day of my participation in the First Challenge 2022

First, write first

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

Question 6: Sum of three numbers, for the interview and born, looking forward to your participation.

Today’s topic

Given an array nums containing n integers, determine whether there are three elements a, B, and c in nums such that a + b + c = 0. Find all the triples that meet the criteria and are not duplicated.

Note: Repeated triples cannot be included in the answer.

Example:

For example, given the array nums = [-1.0.1.2, -1, -4], the set of triples that meet the requirements is: [[-1.0.1], [...1, -1.2]]Copy the code

Three, the analysis

When I first saw this topic, what came to my mind was the sum of two numbers. At first glance, there was no big difference. In fact, it was the difference between two-dimensional space and three-dimensional space.

Initially thought was similar to the sum of two Numbers method, here I want to find the sum of two Numbers is opposite in the list, but really practice, more troublesome, regardless of time complexity, literally said today (Monday) is a trouble thing is thought, so Mr. X decisively abandoned such hair loss thankless approach, in a kind of thought, head + tail search method: The head circulates, the tail searches from both ends to the middle, and the idea is as follows:

Fourth, the problem solving

  • My approach:

Diffusing from the center outward, time complexity: less than O(n^2)

class Solution(object) :
    def threeSum(self, nums) :
		""" :type nums: List[int] :rtype: List[List[int]] """
		# List sort, from smallest to largest
		nums.sort()
		# [-4, -1, -1, 0, 1, 2]
		res_list = []
		# header loop lookup
		for i in range(len(nums)):
			if i == 0 or nums[i] > nums[i - 1] :# the far left
				l = i + 1  
				# the right end
				r = len(nums) - 1
				while l < r:  # search for
					three_sum = nums[i] + nums[l] + nums[r]
					if three_sum == 0:
						res_list.append([nums[i], nums[l], nums[r]])
						l += 1 # Move one to the right
						r -= 1 # move one place to the left
						while l < r and nums[l] == nums[l - 1] :# from left to right, skip the same number directly
							l += 1
						while r > l and nums[r] == nums[r + 1] :# From right to left, skip the same number
							r -= 1
					elif three_sum > 0:
						# is greater than zero, the right-hand side is large, move to the left
						r -= 1
					else:
						# less than zero, small value on the left, right shift
						l += 1
		return res_list
Copy the code
  • Submit the results

Test data: 313 groups running time: 740ms beat percentage :81.35%

Five, doubt

Here’s a reference to zip() from the longest public prefix method in the previous article.

Zip is a Python built-in function that converts arguments (sequence types, strings, primitives, lists) to tuples in traversal order. For example:

a = 'sttd'
b = 'stba'
c = 'sttmss'

for i in zip(a,b,c):
    print(i)
Copy the code

In the previous scenario, we simply iterate over whether the elements in each tuple here are equal or not, which means the same prefix, until we iterate over to unequal, and then we can return the previous value.

As in the figure above, when iterating through (‘t’, ‘b’, ‘t’), the three elements are different, so the longest common prefix of a, b, and c is st.

Six, the concluding

Persistence and hard work: results.

The idea is very complicated,

The implementation is interesting,

As long as you don’t give up,

Fame will come.

— Old Watch doggerel

See you next time. I’m a cat lover and a tech lover. If you find this article helpful, please like, comment and follow me!