Leetcode hot100

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]

Answer:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i]+nums[j] == target:
                    return [i, j]

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1：

输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出：[["bat"],["nat","tan"],["ate","eat","tea"]]

Answer:

class Solution:
    def match(self, str):
        return "".join(sorted(str))

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagram_dict = {}
        for word in strs:
            sorted_word = self.match(word)
            if sorted_word in anagram_dict:
                anagram_dict[sorted_word].append(word)
            else:
                anagram_dict[sorted_word] = [word]
        return list(anagram_dict.values())

128. 最长连续序列

给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 \(O(n)\) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]

输出：4

解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

Answer:

排序的时间复杂度为O(nlogn)!!!因此不能排序

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        ans = 0
        set_nums = set(nums)  # 转为集合去重
        for x in set_nums:
            if x - 1 in set_nums:
                continue
            y = x + 1
            while y in set_nums:
                y += 1
            ans = max(ans, y - x)
        return ans

283. Move Zeroes

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non - zero elements.

Note that you must do this in - place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]

Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]

Output: [0]

Answer 1:

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        count = 0
        for i in nums:
            if i == 0:
                count += 1
        for i in range(len(nums)):
            if nums[i] != 0:
                continue
            for j in range(i+1, len(nums)):
                if nums[j] != 0:
                    nums[i] = nums[j]
                    i += 1 
        for z in range(len(nums)-count, len(nums)):
            nums[z] = 0
        return nums

Answer 2:

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        i0 = 0
        for i in range(len(nums)):
            if nums[i]:
                nums[i], nums[i0] = nums[i0], nums[i]
                i0 += 1
# by：灵茶山艾府

11. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x - axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]

Output: 49

Explanation: The above vertical lines are represented by the array [1,8,6,2,5,4,8,3,7]. In this case, the maximum area of water (the blue - shaded section) that the container can hold is 49.

Example 2

Input: height = [1,1]

Output: 1

Answer 1:

Brute-force search，NONONO

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxarea = 0
        for i in range(len(height)):
            for j in range(i+1, len(height)):
                maxarea = max(maxarea, (j-i)* min(height[j],height[i]))
        return maxarea

Answer 2:

Great !!!

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i , j, maxarea = 0, len(height)-1, 0
        while i < j:
            if height[i] < height[j]:
                maxarea = max(maxarea, (j-i) * height[i])
                i += 1
            else:
                maxarea = max(maxarea, (j-i) * height[j])
                j -= 1
        return maxarea

15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].

Notice that the order of the output and the order of the triplets does not matter.

Answer:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums = sorted(nums)
        i = 0
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:  # i 是可以跳过重复数字的
                continue
            if nums[i] > 0: # 优化1
                break
            if nums[i] + nums[i+1] + nums[i+2] > 0: # 优化2
                break
            if nums[i] + nums[-1] + nums[-2] < 0: # 优化3
                continue
            k = i + 1
            j = len(nums)-1
            while k < j:  # 剩下的问题是两数和
                if nums[i] + nums[k] + nums[j] < 0:
                    k += 1
                elif nums[i] + nums[k] + nums[j] > 0:
                    j -= 1
                else:
                    result.append([nums[i], nums[k], nums[j]])
                    j -= 1
                    while k < j and nums[j] == nums[j+1]:  # j k 排除重复数字时，都是和考虑过的数字比较！！！
                        j -= 1
                    k += 1
                    while k < j and nums[k] == nums[k-1]:
                        k += 1
        return result

3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without duplicate characters.

Example 1:

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3.

Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Answer:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = left = 0
        count  = defaultdict(int) # 使用 defaultdict(int) 不需要预先检查键是否存在
        for right, c in enumerate(s):
            count[c]+=1
            while count[c]>1:
                count[s[left]]-=1
                left+=1
            result = max(result, right - left +1)
        return result

438. Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

Example 1:

Input: s = "cbaebabacd", p = "abc"

Output: [0,6]

Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"

Output: [0,1,2]

Explanation:

The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

考察点是滑动窗口，与前一题有点像

Answer 1:

能够通过大部分样例的解法，比较笨

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        result = []
        length = len(p)
        p = "".join(sorted(p))
        for i in range(len(s)-length+1):
            string = ""
            for j in range(length):
                string += s[i+j]
            string = "".join(sorted(string))
            if string == p:
                result.append(i)
        return result

Answer 2:

采用了定长滑动窗口的解法

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        result = []
        length = len(p)
        cnt_p = Counter(p) # Counter 用于统计可哈希对象的出现次数
        cnt_s = Counter()
        for right, c in enumerate(s):
            cnt_s[c]+=1
            left = right - length + 1
            if left < 0:
                continue
            if cnt_s == cnt_p:
                result.append(left)
            cnt_s[s[left]] -= 1  # 因为定长滑动窗口，所以需要把左边的元素减掉
        return result

Answer 3:

采用不定长滑动窗口，思路参考：by 灵茶山艾府

枚举子串 s' 的右端点，如果发现 s' 其中一种字母的出现次数大于 p 的这种字母的出现次数，则右移 s' 的左端点。如果发现 s' 的长度等于 p 的长度，则说明 s' 的每种字母的出现次数，和 p 的每种字母的出现次数都相同，那么 s' 是 p 的异位词。

证明：内层循环结束后，s' 的每种字母的出现次数，都小于等于 p 的每种字母的出现次数。如果 s' 的其中一种字母的出现次数比 p 的小，那么 s' 的长度必然小于 p 的长度。所以只要 s' 的长度等于 p 的长度，就说明 s' 的每种字母的出现次数，和 p 的每种字母的出现次数都相同，s' 是 p 的异位词，把 s' 左端点下标加入答案。

代码实现时，可以把 cntS 和 cntP 合并成一个 cnt： - 对于 p 的字母 c，把 cnt[p] 加一。 - 对于 s' 的字母 c，把 cnt[c] 减一。 - 如果 cnt[c] < 0，说明窗口中的字母 c 的个数比 p 的多，右移左端点。

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        result = []
        length = len(p)
        cnt_p = Counter(p)
        cnt_s = Counter()
        left = 0
        for right, c in enumerate(s):
            cnt_s[c]+=1
            while cnt_s[c] > cnt_p[c]:
                cnt_s[s[left]] -= 1
                left += 1
            if right - left + 1 == length:
                result.append(left)
        return result

560. Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.
子数组是数组中元素的连续非空序列。
注意是连续的！！！

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

问：为什么这题不适合用滑动窗口做？
答：滑动窗口需要满足单调性，当右端点元素进入窗口时，窗口元素和是不能减少的。本题 nums 包含负数，当负数进入窗口时，窗口左端点反而要向左移动，导致算法复杂度不是线性的。
---by：灵茶山艾府

在解决本题之前，需要练习前缀和模板题303!!!

Answer 1:

前缀和问题，使用前缀和字典记录前缀和的出现次数，然后遍历数组，计算当前前缀和减去目标值k的差值在字典中出现的次数，累加到结果中。

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        prefix_sum = {0: 1}  # 前缀和字典，初始值为前缀和为0出现1次
        current_sum = 0
        count = 0
        for num in nums:
            current_sum += num
            if current_sum - k in prefix_sum:
                count += prefix_sum[current_sum - k]
            prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1
        return count

Answer 2:

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        fsum = [0] * (len(nums) + 1)
        ans = 0
        for index, n in enumerate(nums):
            fsum[index+1] = fsum[index] + n
        cnt = defaultdict(int)
        for s in fsum:
            ans += cnt[s-k]
            cnt[s] += 1
        return ans

Answer 3:

还可以优化成一次遍历即可实现：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        fsum = [0] * (len(nums) + 1)
        ans = 0
        cnt = defaultdict(int)
        cnt[0] = 1
        s = 0
        for n in nums:
            s += n
            ans += cnt[s-k]
            cnt[s] += 1
        return ans

303. Range Sum Query - Immutable

Given an integer array nums, handle multiple queries of the following type:

1. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

• NumArray(int[] nums) Initializes the object with the integer array nums.
• int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"] [[-2, 0, 3, -5, 2, -1], [0, 2], [2, 5], [0, 5]]

Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

303连题目都看不懂。。。绝了。。。

Answer 1:

class NumArray:

    def __init__(self, nums: List[int]):
        self.fsum = [0] * (len(nums) + 1)
        for i, n in enumerate(nums):
            self.fsum[i+1] = self.fsum[i] + n

    def sumRange(self, left: int, right: int) -> int:
        return self.fsum[right+1] - self.fsum[left]

# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)

303做完再回去看560应该就能看懂了

53. Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Answer 1:

遍历解法，能通过绝大多数测试，复杂度为O(n^2)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = -10000
        fsum = [0]* (len(nums)+1)
        for index, n in enumerate(nums):
            fsum[index+1] = fsum[index] + n 
        for i in range(len(nums)+1):
            for j in range(i+1,len(nums)+1):
                ans = max(ans, fsum[j]-fsum[i])
        return ans

Answer 2:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = nums[0]
        current_array = 0
        for n in nums:
            if current_array < 0:
                current_array = n    
            else:
                current_array += n
            ans = max(current_array, ans)
        return ans

这种解法的主角是当前遍历的对象n，如果当前数组的和小于0，那么当前数组的和就等于n，否则就加上n，然后比较当前数组的和和ans的大小，如果当前数组的和大于ans，那么ans就等于当前数组的和

56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping

Answer 1:

class Solution:
    def detect(self, list1, list2):
        if list1[1] < list2[0]:
            return False
        elif list1[0] > list2[1]:
            return False
        else:
            return True
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        intervals.sort(key=lambda x: x[0]) # 按照左端点排序
        ans = [intervals[0]]
        for interval in intervals:
            last_interval = ans[-1]
            if self.detect(last_interval, interval):
                ans[-1] = [min(last_interval[0],interval[0]), max(last_interval[1], interval[1])]
            else:
                ans.append(interval)
        return ans

189. Rotate Array

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Answer 1:

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        # 处理 k 大于数组长度的情况
        k = k % n
        # 创建临时数组存储后 k 个元素
        temp = nums[-k:]
        # 将数组前 n - k 个元素向后移动 k 个位置
        for i in range(n - 1, k - 1, -1):
            nums[i] = nums[i - k]
        # 将临时数组中的元素复制到数组前面
        for i in range(k):
            nums[i] = temp[i]

238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Answer 1:

前后缀分解

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        temp1 = [1]*n
        temp2 = [1]*n
        temp = 1
        ans = [1]*n
        for i in range(1, n):
            temp *= nums[i-1] 
            temp1[i] = temp
        temp = 1
        for i in range(n-1):
            temp *= nums[n-1-i]
            temp2[n-2-i] = temp
        for i in range(n):
            ans[i] = temp1[i]*temp2[i]
        return ans

73. Set Matrix Zeroes

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
You must do it in place.

Example 1:

Answer 1:

解法一采用同等大小的矩阵来记录0的位置，然后遍历矩阵，如果某个位置是0，则将对应的行和列都置为0。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m = len(matrix)
        n = len(matrix[0])
        temp = [0]*(m*n)
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    temp[i*n+j] = 1
        for i in range(m*n):
            if temp[i] == 1:
                M = int(i / n)
                N = int(i % n)
                for j in range(n):
                    matrix[M][j] = 0
                for k in range(m):
                    matrix[k][N] = 0
        return matrix

Answer 2:

官方解法，可读性要更强一点

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        row, col = [False] * m, [False] * n

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    row[i] = col[j] = True
        
        for i in range(m):
            for j in range(n):
                if row[i] or col[j]:
                    matrix[i][j] = 0
作者：力扣官方题解