Ace number two, three, four, and N sum | interview necessary algorithm

The sum of two Numbers

The title

Given an integer array nums and an integer target value target, find the two integers in the array and the target values and return their array subscripts. You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer. You can return the answers in any order.Copy the code

Example 1:

Input: nums = [2,7,11,15], target = 9 output: [0,1]Copy the code

Example 2:

Input: nums = [3,2,4], target = 6Copy the code

Example 3:

Input: nums = [3,3], target = 6Copy the code

Tip:

2 <= nums.length <= 103-109 <= nums[I] <= 109-109 <= target <= 109Copy the code

The problem solving

The question can be answered in three ways

The enumeration of violence

The easiest way to think about it is a double-layer traversal enumerationnums, the querynums[i] + nums[j] = target

Algorithm source code:

class Solution(object) :
    def twoSum(self, nums, target) :
        """ :type nums: List[int] :type target: int :rtype: List[int] """
        # 1. The violence
        for i in range(len(nums) - 1) :for j in range(i + 1.len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []
Copy the code

Time complexity: O(N^2), where N is the number of elements in the array. In the worst case, all the numbers in the array need to be matched

Sort + double pointer

The querynums[i] + nums[j] = targetIt’s also easy to think of a double pointer, but a double pointer requires an ordered array, so sort the array first and keep the original index

nums = [[i, v] for i, v in enumerate(nums)]
nums = sorted(nums, key=lambda k: k[1], reverse=False)
Copy the code

Algorithm source code:

class Solution(object) :
    def twoSum(self, nums, target) :
        """ :type nums: List[int] :type target: int :rtype: List[int] """
        # 2. Sort + double pointer
        nums = [[i, v] for i, v in enumerate(nums)]
        nums = sorted(nums, key=lambda k: k[1], reverse=False)
        start, end = 0.len(nums) - 1
        while start < end:
            tmp_sum = nums[start][1] + nums[end][1]
            if tmp_sum < target:
                start += 1
            elif tmp_sum > target:
                end -= 1
            else:
                return [nums[start][0], nums[end][0]]
        return []
Copy the code

Time complexity: O(NlogN), where the array is sorted O(NlogN), and then the double pointer traverses O(N) to get the result space complexity: O(N), where N is the number of elements in the array

The hash

Above method querytarget - xThe time complexity is high, so to quickly query the array for target elements, we can use indexes. Using a hash table, you can look fortarget - xTime complexity is reduced fromO(N)Down toO(1)

Algorithm source code:

class Solution(object) :
    def twoSum(self, nums, target) :
        """ :type nums: List[int] :type target: int :rtype: List[int] """
        # 3. The hash
        hash_res = {}
        for k, v in enumerate(nums):
            if target - v in hash_res:
                return [hash_res[target - v], k]
            hash_res[v] = k
        return []
Copy the code

Time complexity: O(N), where N is the number of elements in the array. For each element x, we can look O(1) for the target-x space complexity: O(N), where N is the number of elements in the array. Mainly the overhead of the hash table

The sum of three number

The title

Given an array nums containing n integers, determine if there are three elements a, B, and c in nums such that a + b + c = 0. Please find all the triples that sum to 0 and are not repeated. Note: Repeated triples cannot be included in the answer.Copy the code

Example 1:

Input: nums = [1, 2, 1, 4] output: [[1, 1, 2], [1, 1]]Copy the code

Example 2:

Nums = [] Output: []Copy the code

Example 3:

Input: nums = [0]Copy the code

Tip:

0 <= nums.length <= 3000
-105 <= nums[i] <= 105
Copy the code

The problem solving

Sort + iteration 1 + double pointer

The core of the problem isnums[k] + nums[i] + nums[j] = targetThe formula, if fixednums[k]It is easy to think of the sum of two numbers (sort + double pointer) solution.

The original list: [1, 2, 1, 4] sorted: [- 4, 1, 1, 2] ^ ^ ^ fixed k, I, j, double needle methodCopy the code

Therefore, the solution of sorting + double pointer can be modified by adding a loop to the outer layer. The pseudocode is as follows

For k, V in enumerate(nums[:-2]): #Copy the code

Notice the critical conditionslen(nums) < 3Judgments and triples do not repeat judgments

Algorithm source code:

class Solution(object) :
    def threeSum(self, nums) :
        """ :type nums: List[int] :rtype: List[List[int]] """
        if len(nums) < 3: return [] # Critical judgment
        nums = sorted(nums, reverse=False)
        res = set(a)# to heavy
        for i, v in enumerate(nums[:-2) :if v > 0: break         # Prune optimization
            start, end = i + 1.len(nums) - 1
            while start < end:
                if v + nums[start] + nums[end] > 0:
                    end -= 1
                elif v + nums[start] + nums[end] < 0:
                    start += 1
                else:
                    temp = (v, nums[start], nums[end])
                    Sorted (temp, reverse=False
                    res.add((temp[0], temp[1], temp[2]))
                    start += 1
        return list(res)
Copy the code

Time complexity: O(N^2), sort O(NlogN) + query comparison O(N^2) space complexity: O(N), where N is the number of elements in the array

The sum of four number

The title

Given an array nums containing n integers and a target value target, determine whether there are four elements a, B, c, and D in nums such that a + b + C + D is equal to target. Find all quaternions that meet the condition and are not duplicated. Note: repeated quads cannot be included in the answer.Copy the code

Example 1:

Input: nums = (1, 0, 1, 0, 2, 2], target = 0 output: [[,1,2-2-1], [2,0,0,2], [1,0,0,1]]Copy the code

Example 2:

Input: nums = [], target = 0Copy the code

Tip:

0 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
Copy the code

The problem solving

Sort + iterate twice + double pointer

Nums [k] + NUMs [m] + NUMs [I] + nums[j] = target
Therefore, the solution of the sum of three numbers can be reconstructed by adding a loop to the outer layer. The pseudocode is as follows

For k, V in enumerate(nums[:-3]): #Copy the code

Algorithm source code:

class Solution(object) :
    def fourSum(self, nums, target) :
        """ :type nums: List[int] :type target: int :rtype: List[List[int]] """
        if len(nums) < 4: return []
        nums = sorted(nums, reverse=False)
        res = set(a)# to heavy
        for i, i_v in enumerate(nums[:-3) :for j, j_v in enumerate(nums[i + 1: -2]):
                start, end = i + j + 2.len(nums) - 1
                while start < end:
                    sum_val = i_v + j_v + nums[start] + nums[end]
                    if sum_val > target:
                        end -= 1
                    elif sum_val < target:
                        start += 1
                    else:
                        temp = [i_v, j_v, nums[start], nums[end]]
                        # temp = sorted(temp, reverse=False)
                        res.add((temp[0], temp[1], temp[2], temp[3]))
                        start += 1
        return list(res)
Copy the code

Time complexity: O(N^3), sort O(NlogN) + query comparison O(N^3) space complexity: O(N), where N is the number of elements in the array

The sum of N number

Sort + recursive iteration N-1 times + double pointer

With the sum of two, the sum of three, the sum of four, then the sum of five, and the sum of N… Is there a universal method? In this case, we can use this general pattern. Sum of four numbers and extend to sum of N numbers

Algorithm code:

class Solution(object) :
    def fourSum(self, nums, target) :
        """ :type nums: List[int] :type target: int :rtype: List[List[int]] """
        # 2. Generic recursive methods
        def nSum(nums, n, target) :
            if len(nums) < n: return []
            res = []
            if n == 2:
                left, right = 0.len(nums)-1
                while left < right:
                    if nums[left] + nums[right] == target:
                        res.append([nums[left], nums[right]])
                        while left < right and nums[left] == nums[left+1]: left += 1
                        while left < right and nums[right] == nums[right-1]: right -= 1
                        left += 1
                        right -= 1
                    elif nums[left] + nums[right] > target:
                        right -= 1
                    else:
                        left += 1
                return res
            else:
                for i in range(len(nums)):
                    if i > 0 and nums[i] == nums[i - 1] :continue
                    sub_res = nSum(nums[i + 1:], n - 1, target - nums[i])
                    for j in range(len(sub_res)): res.append([nums[i]] + sub_res[j])
                return res

        if len(nums) < 4:   return []
        nums = sorted(nums, reverse=False)
        return nSum(nums, 4, target)
Copy the code

conclusion

The sum of N numbers can be processed by the last template code, but because the whole core is reduced by a layer of traversal through double Pointers, the overall performance is limited if the N value is too large

The appendix

Leetcode-cn.com/problems/tw…
Leetcode-cn.com/problems/3s…
Leetcode-cn.com/problems/4s…

❤️❤️❤️ Every love from readers is my motivation! I am SAN Tu, thank you friends: like, favorites and comments, we will see you next time!

Ace number two, three, four, and N sum | interview necessary algorithm

The sum of two Numbers

The title

The problem solving

The enumeration of violence

Sort + double pointer

The hash

The sum of three number

The title

The problem solving

Sort + iteration 1 + double pointer

The sum of four number

The title

The problem solving

Sort + iterate twice + double pointer

The sum of N number

Sort + recursive iteration N-1 times + double pointer

conclusion

The appendix

Related Posts

Escape analysis, scalar replacement, allocation on the stack

LeetCode — 739. Daily temperature

Hand Tear Design Patterns – Overview