Topic description

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Now given an array of n integers, look for three numbers that add up to 0. Find all the different groups, each group consists of three numbers, and the sum of the three numbers is 0

Note:

The solution set must not contain duplicate triplets.

The rightmost result must be the set of repeated combinations without

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

Constraints: (limit)

0 <= nums.length <= 3000，The length of the array is less than 3000
-105 <= nums[i] <= 105，The element size of the array is±105 between

Thought analysis

• Notice:

  • You cannot convert the list to a set, eliminate all the same elements, and the same elements can also add up to 0, such as 1, 1, -2
  • Make sure that the input list has three or more elements, otherwise there is no way to form a set

Brute-force cracking:

*Three kinds of loops, list all three-element combinations, and determine whether the addition is 0
* Determine if the last composition is in the set, if not, add it

• Question: In python, if the elements of the list are the same, but the positions are different, is it the same list?
• Answer: First of all, lists cannot be used as elements of sets. The data elements of sets must be hashable and immutable data types. Lists are mutable data types and cannot be used. If it is replaced by a tuple, the order is different, and it is still a different element. So it is not advisable to sort the elements before forming a tuple.

Code

python - law of violence

class Solution(object):
    def threeSum(self, nums):
        result = set()
        result2 = list()
        if len(nums)>=3:
              for i in range(len(nums)-2):
                  for j in range(i + 1,len(nums)- 1):
                      for k in range(j + 1,len(nums)):
                          if(nums[i] + nums[j] + nums[k] == 0):
                              result.add(tuple(sorted((nums[i],nums[j],nums[k]))))
              for i in range(len(result)):
                  result2.append(list(result.pop()))
              return result2
        else:
              return []

if __name__ == '__main__':
    test = Solution()
    nums = [-1,0,1,2,-1,-4]
    print(type(nums))
    print(test.threeSum(nums))

Test Results

• Sure enough, the running time exceeded the limit, and I was stumbling when I wrote it myself. I just started using python, and I almost forgot what I learned before.
• But to be honest, if I implement this method in C language, I don't have to write it, there are too many, it is difficult to just remove the same elements from the collection.
• problems encountered

  • To create an object using a class in python, you need to add parentheses after the class name. If you don't add it, the following exception will occur. Object is not initialized.

  • The elements in the collection have requirements and must be immutable data structures, elements, strings, etc.; no mutable data structures, such as lists and dictionaries, can be used as elements.

  • Tuples with the same elements but in a different order are still different tuples

Improvement - how to reduce the time and number of traversals

• Sort all the numbers into two arrays, positive and negative, with zero counted separately. In the end, zero can be formed, except for the extreme case of three zeros, there must be a positive number and a negative number.
• Take a positive number and a negative number respectively, find all the combinations, and then search in the original array according to the sum of the two
• At most 3000 elements, after all, there are a total of 15000*15000 combinations, which is not practical at all. Each combination also traverses the complete array once, which is not cost-effective.

Reference tutorial

Solution

• For repeated numbers: sort the list, the same numbers must be together after sorting, so you can skip it directly
• Combination of repetitions: fixed position, convert 3Sum into 2Sum, and avoid repetition in 2Sum, if the left and right boundary points are the same after moving, skip it

icon

Code

def threeSum(self,nums):
    result = list()
    if len(nums) >= 3:
        # Sort the original array to mask the effect of duplicate numbers
        nums.sort()
        # Divided into two traversals, the outermost traversal is to determine the first position where the three numbers are added, and the problem is simplified to 2Sum, and the second level of traversal is to determine the problem of solving 2Sum
        i = 0
        while i < len(nums):
            left = i + 1
            right = len(nums) - 1
            while left < right:
                if nums[left] + nums[right] == 0 - nums[i]:
                    result.append([nums[i], nums[left], nums[right]])

                    temp = 1
                    while left + temp < len(nums) and nums[left + temp] == nums[left]:
                        temp += 1
                    left = left + temp

                    temp = 1
                    while nums[right - temp] == nums[right]:
                        temp += 1
                    right = right - temp
                elif nums[left] + nums[right] > 0 - nums[i]:
                    temp = 1
                    while nums[right - temp] == nums[right]:
                        temp += 1
                    right = right - temp
                else:
                    temp = 1
                    while left + temp < len(nums) and nums[left + temp] == nums[left]:
                        temp += 1
                    left = left + temp
            temp = 1
            while i + temp < len(nums) and nums[i + temp] == nums[i]:
                temp += 1
            i += temp
        return result
    else:
        return []

operation result

Analysis and Summary

• In actual operation, pay attention to the out-of-bounds problem of the array, whether it is the left boundary point or the right boundary point, it must be controlled
• Going over all the same data methods, set the base step to 1, then increment by 1 item by item to get the final result.

Reference Code

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        
        for i, a in enumerate(nums):
            if i > 0 and a == nums[i - 1]:
                continue
            # After the iteration, first determine whether the value is the same as the previous value. If it is the same, skip it directly and go to the next loop.
            
            l, r = i + 1, len(nums) - 1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                if threeSum > 0:
                    r -= 1
                elif threeSum < 0:
                    l += 1
                # If the encounters are the same, there is no need to determine whether they are the same, the same will not play a role in reducing or increasing
                else:
                    res.append([a, nums[l], nums[r]])
                    l += 1
                    while nums[l] == nums[l - 1] and l < r:
                        l += 1
                    # There is no need to shrink both sides at the same time, just change one side and the other side will automatically balance
        return res

Analysis and Summary

• enumerate(): Combine a traversable data object into an index sequence, and list data and data subscripts at the same time, generally used in for loops
  • enemerate (objects that can be traversed, where to start traversing)

>>>seq = ['one', 'two', 'three']
>>> for i, element in enumerate(seq):
...     print i, element
... 
0 one
1 two
2 three