Leetcode 两数之和&三数之和 5题[双指针]

简单题:

  1. 两数之和
  2. 两数之和 II - 输入有序数组
  3. 两数之和 IV - 输入 BST

中等题:
15. 三数之和
16. 最接近的三数之和

1. 两数之和

file

解法

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for index, value in enumerate(nums):
            res = target - value
            if(res in hashmap):
                return(hashmap[res],index)
            hashmap[value]=index
		# Method 2
        # for i in range(len(nums)):
        #     j = len(nums) - 1
        #     while(j > i):
        #         if(nums[i] + nums[j] == target):
        #             return [i,j]
        #         j -= 1
 

Note:

  • 方法2是暴搜
  • 方法1是遍历数组建立哈希表,并检查剩余目标分数是否存在哈希表里,在则返回。

167. 两数之和 II - 输入有序数组

file

解法

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # hashmap = {}
        # for index,value in enumerate(numbers):
        #     res = target - value
        #     if res in hashmap:
        #         return [hashmap[res]+1,index+1]
        #     hashmap[value] = index
        i = 0
        j = len(numbers) - 1
        while(j > i):
            if numbers[i] + numbers[j] == target:
                return [i + 1,j + 1]
            #   如果比目标值小,我们将较小元素指针增加一。如果比目标值大,我们将较大指针减小一
            elif(numbers[i] + numbers[j] < target):
                i += 1
            else:
                j -= 1
 

Note:

  • 用前面提到的哈希表做也是可以的 完全相同的解法,时间复杂度O(n),空间复杂度O(n)
  • 双指针解法,充分利用数组已排好序的性质。指针变动条件已在注释中自明,注意这个思想在后面三数之和、四数之和等也会用到

653. 两数之和 IV - 输入 BST

file

解法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def findTarget(self, root: TreeNode, k: int) -> bool:
stack = []
p = root
nums = []
while(stack or p):
if(p):
stack.append(p)
p = p.left
else:
p = stack.pop()
nums.append(p.val)
p = p.right
hashmap = {}
for index,value in enumerate(nums):
res = k - value
if res in hashmap:
return True
hashmap[value] = index
return False


 

Note:

  • 其实主要是复习了下中序/前序/后序(还没整明白) 非递归遍历二叉树。。。
  • 我好菜啊 全不会写了。。。唉

15. 三数之和

file

解法

class Solution:
    def threeSum(self, nums: [int]) -> [[int]]:
        nums.sort()
        res, k = [],0
        for k in range(len(nums)-2):
            if nums[k] > 0:
                break
            if k>0 and nums[k] == nums[k-1]:
                continue
            i, j = k+1, len(nums) - 1
            while(i < j):
                s = nums[k] + nums[i] + nums[j]
                if(s == 0):
                    res.append([nums[k], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    while i < j and nums[i] == nums[i-1]:
                        i += 1
                    while i < j and nums[j] == nums[j+1]:
                        j -= 1
                elif(s < 0):
                    i += 1
                    while i < j and nums[i] == nums[i - 1]:
                        i += 1
                elif(s > 0):
                    j -= 1
                    while i < j and nums[j] == nums[j + 1]:
                        j -= 1
        return res
 

Note:

  • 很多细节 很烦人
  • 思想: 遍历数组 记当前下标为i,固定当前下标i,取j = i + 1,k = len(nums) - 1,计算三数之和,再根据实际情况移动j , k。

16. 最接近的三数之和

file

解法

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        k = 0
        min_flag = float('inf')
        res = float('inf')
        for k in range(len(nums) - 2):
            i, j = k + 1,len(nums) - 1
            while(i < j):
                s = nums[k] + nums[i] + nums[j]
                if(abs(s-target) < min_flag):
                    min_flag = abs(s-target)
                    res = s
                elif s > target:
                    j -= 1
                else:
                    i += 1
        return res
 

Note:

  • 比15题简单些,解答案唯一所以不用考虑重复数字的情况。

我太菜了 慢慢来┭┮﹏┭┮

好消息:本站已经开放注册啦。