LeetCode classification: find two

Find actual combat

Case 1: sum of two numbers

Given an integer array nums and a target value target, please find the two integers with and as the target value in the array and return their array subscripts.
You can assume that each input will correspond to only one answer. However, the same element in the array cannot be used twice.
Example:

Given, target = [11, nums, 2], target = [15, nums]
Because num [0] + num [1] = 2 + 7 = 9
So [0, 1] is returned

The idea of problem solving first thinks of violent solution, that is, traversing the array for the first time and the elements after the current traversal value for the second time, but the time complexity is O(n^2).
So I want to optimize and use the binary search method to sort the input array first (from small to large), but the index of elements will also change. Therefore, before sorting, I use an additional array to copy an original array. For the index problem of two identical elements, I use a bool variable to help find both indexes. The total time complexity is O(n)+O(nlogn) = O(nlogn)
The code is as follows:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = dict()
        nums_copy = nums.copy()
        sameFlag = True;
        nums.sort()
        l,r = 0,len(nums)-1
        while l < r:
            if nums[l] + nums[r] == target:
                break
            elif nums[l] + nums[r] < target:
                l += 1
            else:
                r -= 1
        res = []
        for i in range(len(nums)):
            if nums_copy[i] == nums[l] and sameFlag:
                res.append(i)
                sameFlag = False
            elif nums_copy[i] == nums[r]:
                res.append(i)
        return res

However, there is another more convenient solution, which starts to realize the binding of subscript and value through list (enumerate (Num)), without special copy and bool judgment.
The code is as follows:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # res = dict()
        # for index in range(len(nums)):
        #     res[nums[index]] = index
        # for i,num in enumerate(nums):
        #     j = res.get(target-num)
        #     if j is not None and j!=i:
        #         return [i,j]
        nums = list(enumerate(nums))
       

        nums.sort(key =lambda x:x[1])
        print(nums)
        l = 0
        r = len(nums)-1
        while l<r:
            if nums[l][1]+nums[r][1] == target:
                return [nums[l][0],nums[r][0]]
            elif nums[l][1]+nums[r][1] < target:
                l +=1
            else:
                r -=1

Case 2: sum of two numbers

Tags: Python Algorithm data structure leetcode

Posted by onewaylife on Fri, 20 May 2022 12:03:25 +0300