当前位置：首页 > article >正文

Leetcode 1. 两数之和

article 2025/1/23 4:08:52

在这里插入图片描述

心路历程：

很简单的题，双层暴力就可以，用双指针的话快一点。暴力时间复杂度O( $n^2$ )，双指针时间复杂度O(nlogn) + O(n) + O(n) = O(nlogn)。

注意的点：

1、题目需要返回原数组的索引，所以排序后还需要对应原数组，还好只要返回唯一解。
2、对应原数组的时候注意处理两个指针赋值不能相同的情况（无法直接用.index()）
3、right指针大于left指针即可，总是有时候把左右指针写反。

解法：排序、双指针、返回对应原数组索引

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 双指针
        newnums = sorted(nums)
        left = 0
        right = len(nums) - 1
        while right > left: 
            if newnums[left] + newnums[right] == target:
                break
            elif newnums[left] + newnums[right] > target:
                right -= 1
            else:
                left += 1
        assert left != right
        
        l1, l2 = 0, 0
        flag = False
        for i in range(len(nums)):
            if newnums[left] == nums[i] and not flag:
                l1 = i
                flag = True
            elif newnums[right] == nums[i]:
                l2 = i
        return [l1, l2]