+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-07(2)

2019-08(89)

2019-09(94)

2019-10(15)

2019-11(5)

1. 两数之和(哈希表) 15. 三数之和(双指针) 18. 四数之和

发布于2020-11-09 17:38     阅读(710)     评论(0)     点赞(1)     收藏(5)


0

1

2

3

4

5

6

7

1 两数之和

https://leetcode-cn.com/problems/two-sum/
在这里插入图片描述
python
在这里插入图片描述

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

2 三数之和

在这里插入图片描述
python

from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        # 枚举 a
        for first in range(n):  # 遍历所有元素
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合,随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])

        return ans


print(Solution().threeSum([3, 5, 4, 4, -2, -2, -1, -3, -3]))

3 四数之和

https://leetcode-cn.com/problems/4sum/solution/si-shu-zhi-he-by-leetcode-solution/
在这里插入图片描述

原文链接:https://blog.csdn.net/x1131230123/article/details/109560656

0

1

2

3

4

5



所属网站分类: 技术文章 > 博客

作者:天青色等烟雨

链接: https://www.pythonheidong.com/blog/article/611751/96a0d4c7210f18673756/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

1 0
收藏该文
已收藏

评论内容:(最多支持255个字符)