leetcode-1

1. 1. 两数之和

  • 一遍哈希表：O(n)
    • 一边更新哈希表一边查询
    • ps：如果用数组做，还要填一遍零

2. 15. 三数之和

  • 转换为两数之和

    • 先排序去重：回归到两数之和
      • 如何去重：直接改set
    • 区别：两数之和问题仅假设有一组
    • 注意：保持升序，利用set特性

  • 假如序列无重复：

    1
    2
    3
    4
    5
    6
    7
    class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            nums,s = sorted(nums),set()
            for i in range(len(nums)-2):
                d={-nums[i]-n:1 for n in nums[i+1:]}
                s.update(frozenset({nums[i],n,-nums[i]-n}) for n in nums[i+1:] if n in d and n != -nums[i]-n)
            return list(map(list, s))

3. 16. 最接近的三数之和

排序，遍历，双指针，O(N^2) 时间复杂度，二分法初始化

双指针法有时也叫快慢指针，在数组里是用两个整型值代表下标，在链表里是两个指针，一般能实现O（n）的时间解决问题，两个指针的位置一般在第一个元素和第二个元素或者第一个元素和最后一个元素，快指针在前“探路”，当符合某种条件时慢指针向前挪

  • head为快，tail为慢
    • head在循环中动态初始化
    • 注意h+(s<target),t-(s>target)不能等于，要至少隔一个
1
2
3
4
5
6
7
8
9
10
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums, ans, end = sorted(nums), float('inf'), len(nums)-1
        for i in range(len(nums)-2):
            h, t = max(i+1, bisect.bisect_left(nums,target -
                                               nums[end] - nums[i], i + 1, end)-1), end
            while ans!=target and h<t:
                s=nums[i]+nums[h]+nums[t]
                h,t,ans = h+(s<target),t-(s>target),min(ans,s,key=lambda x: abs(x-target))
        return ans

4. 3. 无重复字符的最长子串

  • 滑动窗口:双指针:O(n)
    • i指针记录头
    • c指针移动
    • d字典记录c指针指向数值的最大位置
    • 精髓:i=max(i, d.get(c, -1) + 1)更新i指针

5. 5. 最长回文子串