考察知识点:

思路总结:

具体题目:

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
 
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

python3代码实现:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        new_nums = list(zip([i for i in range(len(nums))], nums))
        start_number = 0

        for j in range(len(new_nums)):
            needle_1 = start_number
            needle_2 = start_number + 1
            need_the_value_of_answer = target - new_nums[needle_1][1]

            for k in new_nums[needle_2::]:
                if k[1] == need_the_value_of_answer:
                    position = [needle_1, k[0]]
                    break
                else:
                    pass
            start_number += 1
        
        return position
LeetCode 1. 两数之和插图

———————————————————————————————————————————

因为用了两层for循环,所以时间复杂度会变成O(N的平方), 为了减小时间复杂度,要换一种思想:

首先,当遍历过一个元素的时候,这个元素永远都不会对之后的操作造成任何影响;

另外,最好使用原地置换的方式,这样可以节省一些内存。

因此思路为:

当for循环nums列表的时候,遍历是从列表的头开始的,假想存在着一个从头开始的指针,不断向后移动,让程序可以有结束的条件,即遍历完成就结束。

然后,在指针指向一个元素的时候,向临时列表中添加这个元素,并改变这个元素的值为不会用到的符号,当使用index索引目标值的时候不会索引到这个元素了。如果在nums除去当前元素的剩余元素当中,存在着一个元素满足条件,就中止整个循环,并将那个元素的索引添加到临时列表当中,这时临时列表当中就有两个元素了,返回即可;不过如果这个nums列表当中没有符合条件的值,就将临时列表当中的那个索引值删了,同时还要将已经指向过的这个元素值置换为不会用到的符号,然后继续跟随着指针向后移动,直到循环结束。

python3代码为:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        temp = []
        for elem in nums:
            x = nums.index(elem)
            temp.append(x)
            nums[temp[0]] = "z"
            if (target-elem) in nums:
                y = nums.index(target-elem)
                if y == temp[0]:
                    nums[y] = "x"
                else:
                    temp.append(y)
                    break
            else:
                temp = []
        return temp
LeetCode 1. 两数之和插图1

上面的时间上来看,还是不够快,看看如何优化一下代码?

优化代码的时候,针对现有的代码进行review,问自己究竟为什么要写这行代码,这行代码一定要写吗?

20220214更新了一下,双指针的领悟能力增强

两数之和 II – 输入有序数组
给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列  ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间
作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/all-about-array/x9i1x6/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 双指针,一个指向列表首,一个指向列表尾
        # 移动方式:
        # 首尾相加,       如果大于target,尾指针向左移动一位
        #                 如果等于或者小于target,与首指针的值相加,与target比
        #                 比target小,首指针右移;比target大,尾指针左移
        # 结束条件,符合条件的值对出现或首尾指针相遇
        
        p_1 = 0
        p_2 = len(numbers)-1
        tmp = []

        while len(tmp)==0 and p_1 != p_2:
            if numbers[p_2] + numbers[p_1] == target:
                tmp.append(p_1 + 1)
                tmp.append(p_2 + 1)
            elif numbers[p_2] + numbers[p_1] > target:
                p_2 -= 1
            else:
                p_1 += 1

        if len(tmp) == 0:
            return []
        else:
            return tmp
LeetCode 1. 两数之和插图2

02220310 重做了一下,用一个指针就可以了

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 指针移动,找对应就好了
        p_0 = 0
        back_up = copy.deepcopy(nums)
        while p_0 <= len(nums) - 1:
            other_one = target - nums[p_0]

            nums[p_0] = "x"
            if other_one in nums:
                return [p_0, nums.index(other_one)]
            
            p_0 += 1
            nums = back_up
LeetCode 1. 两数之和插图3

作者 admin

在 “LeetCode 1. 两数之和” 有 1 条评论

发表回复

您的电子邮箱地址不会被公开。