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应该就能看懂了