数组

二分查找

当题干中出现了有序数组和无重复元素时就可以考虑使用二分查找来进行解题。二分查找的框架是定义一个搜索区间[left, right]，然后利用中间元素mid来不断更新区间：

left, right = 0, len(arr)-1

while left <= right:
    mid = left + (right-left) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

需要注意的是在更新区间端点时要把left和right更新为mid + 1和mid - 1。这是因为我们已经检查过中点mid对应的元素一定不是目标target，也就无需再考虑mid位置。

704. 二分查找

给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的 target，如果目标值存在返回下标，否则返回-1。

示例1：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例2：

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设nums中的所有元素是不重复的
n将在[1, 10000]之间
nums的每个元素都将在[-9999, 9999]之间

Solution

题目链接：

python代码：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1

        while left <= right:
            mid = left + (right-left) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

C++代码：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left  = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid+1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
};

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为O(log n)的算法。

示例 1：

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2：

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3：

输入: nums = [1,3,5,6], target = 7
输出: 4

提示：

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums为无重复元素的升序排列数组
-10⁴ <= target <= 10⁴

Solution

当target存在于nums数组中时使用标准的二分查找即可；而当target不在nums中时我们需要返回数组中首个大于target的元素位置，此时它即为退出搜索循环时left的位置。

题目链接：

python代码：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        
        while left <= right:
            mid = left + (right-left) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return left

C++代码：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left  = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值target，返回[-1, -1]。

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

示例 1：

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2：

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

示例 3：

输入: nums = [], target = 0
输出: [-1,-1]

提示：

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
nums是一个非递减数组
-10⁹ <= target <= 10⁹

Solution

当数组中有重复的target时，使用二分查找会得到重复区间中的某个位置。此时为了得到重复区间的边界，只需分别向左右进行搜索即可。

题目链接：

python代码：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if len(nums) == 0:
            return [-1, -1]
        
        def binarySearch(nums: List[int]) -> int:        
            left, right = 0, len(nums)-1

            while left <= right:
                mid = left + (right-left) // 2

                if nums[mid] == target:
                    return mid
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            
            return -1
        
        idx = binarySearch(nums)
        if idx == -1:
            return [-1, -1]

        left, right = idx, idx
        while left-1 >= 0 and nums[left-1] == target:
            left -= 1

        while right+1 <= len(nums)-1 and nums[right+1] == target:
            right += 1
        
        return [left, right]

C++代码：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int mid = binarySearch(nums, target);

        if (mid == -1) return vector<int>{-1, -1};

        int left, right;
        left = right = mid;

        while (left >= 1 && nums[left-1] == nums[mid]) {
            left--;
        }

        while (right+1 <= nums.size()-1 && nums[right+1] == nums[mid]) {
            right++;
        }

        return vector<int>{left, right};
    }

    int binarySearch(vector<int>& nums, int target) {
        int left  = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
};

69. x的平方根

给你一个非负整数x，计算并返回x的算术平方根。

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

注意：不允许使用任何内置指数函数和算符，例如pow(x, 0.5)或者x ** 0.5。

示例 1：

输入: x = 4
输出: 2

示例 2：

输入: x = 8
输出: 2
解释: 8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 2³¹ - 1

Solution

使用二分法进行解题时我们需要稍微修改一下判断条件，当中点mid的平方小于等于x且mid+1的平方大于x时退出搜索。

题目链接：

python代码：

class Solution:
    def mySqrt(self, x: int) -> int:
        def cond(xx):
            if xx*xx <= x and (xx+1)*(xx+1) > x:
                return True
            return False
        
        left, right = 0, x
        while left <= right:
            mid = left + (right-left) // 2

            if cond(mid):
                return mid
            elif mid*mid < x:
                left = mid+1
            else:
                right = mid-1
        
        return mid

C++代码：

class Solution {
public:
    int mySqrt(int x) {
        int left  = 0;
        int right = x;
        int res   = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if ((long long) mid*mid <= x) {
                left = mid + 1;
                res  = mid;
            } else {
                right = mid - 1;
            }
        }

        return res;
    }
};

当然更快的解法是使用牛顿法，迭代式为：

\[\begin{aligned} y &\leftarrow y - \frac{y^2-x}{2y} \\ &\leftarrow \frac{y}{2} + \frac{x}{2y} \end{aligned}\]

python代码：

class Solution:
    def mySqrt(self, x: int) -> int:
        y = x

        while y*y > x:
            y = y/2+x/(2*y)
            y = int(y)
        
        return y

C++代码：

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;

        double xi = x;
        double xj = (xi + x / xi) / 2;

        while (abs(xi - xj) > 1e-7) {
            xi = xj;
            xj = (xi + x / xi) / 2;
        }

        return (int) xj;
    }
};

367. 有效的完全平方数

给你一个正整数num。如果num是一个完全平方数，则返回true，否则返回false。

完全平方数是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如sqrt。

示例 1：

输入: num = 16
输出: true
解释: 返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：

输入: num = 14
输出: false
解释: 返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

提示：

1 <= num <= 2³¹ - 1

Solution

题目链接：

python代码：

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num == 1:
            return True

        left, right = 1, num-1

        while left <= right:
            mid = left + (right-left) // 2
            mid2= mid*mid

            if mid2 == num:
                return True
            elif mid2 < num:
                left = mid + 1
            else:
                right = mid - 1
        
        return False

C++代码：

class Solution {
public:
    bool isPerfectSquare(int num) {
        int left  = 0;
        int right = num;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            long long square = static_cast<long long>(mid) * mid;

            if (square == num) {
                return mid;
            } else if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
};

除了二分法之外，更快的方法是利用完全平方数的性质。实际上完全平方数可以表示为等差数列的和：

1×1 = 1
2×2 = 1 + 3
3×3 = 1 + 3 + 5
4×4 = 1 + 3 + 5 + 7
…
n×n = 1 + 3 + … + (2n-1)

因此我们只需要判断num是否能够分解为这样的等差数列即可。

python代码：

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        i = 1
        while num > 0:
            num -= i
            i += 2
        
        return num == 0

C++代码：

class Solution {
public:
    bool isPerfectSquare(int num) {
        int i = 0;

        while (num > 0) {
            num = num - (2*i + 1);
            ++i;
        }

        return num == 0;
    }
};

双指针

双指针的基本思想是使用两个指针来遍历数组，很多需要使用二重循环的问题通过双指针就只需一次循环就能解决，这样算法的复杂度就由O(n²)降低为O(n)。

26. 删除有序数组中的重复项

给你一个升序排列的数组nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有k个元素，那么nums的前k个元素应该保存最终结果。

将最终结果插入nums的前k个位置后返回k。

不要使用额外的空间，你必须在原地修改输入数组并在使用 O(1)额外空间的条件下完成。

判题标准：

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被通过。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 * 10⁴
-10⁴ <= nums[i] <= 10⁴
nums已按升序排列

Solution

本题是数组双指针的经典问题，我们需要使用两个指针fast和slow对nums进行遍历。当快指针fast与其前一个位置具有相同的值时继续前进，否则就把fast指针的值赋给slow并令slow += 1，这样慢指针slow始终指向nums中去除重复元素后的下一位。完成遍历后返回slow即可。

题目链接：

python代码：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        N = len(nums)
        if N == 1:
            return N

        fast, slow = 0, 0

        for fast in range(N):
            if fast > 0 and nums[fast-1] == nums[fast]:
                continue
            
            nums[slow] = nums[fast]
            slow += 1

        return slow

C++代码：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int N = nums.size();
        if (N == 1) return N;

        int slow = 1;

        for (int fast=1; fast < N; ++fast) {
            if (nums[fast] != nums[fast-1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
        }

        return slow;
    }
};

27. 移除元素

给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用O(1)额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

Solution

这个问题可以使用快慢两个指针来进行处理：快指针fast直接对数组进行遍历，而慢指针slow则对应不包含val的新数组。当快指针fast遇到val时保持慢指针slow不动，这样可以保证新数组不会包含val；否则就把fast位置的值赋给slow，这样就更新了数组；最后慢指针slow的位置即为所需的新数组长度。整个算法过程可以可视化如下：

题目链接：

python代码：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        fast, slow = 0, 0

        for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1

        return slow

C++代码：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;

        for (int fast = 0; fast < nums.size(); ++fast) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                ++slow;
            }
        }

        return slow;
    }
};

283. 移动零

给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2：

输入: nums = [0]
输出: [0]

提示：

1 <= nums.length <= 10⁴
-2³¹ <= nums[i] <= 2³¹-1

Solution

解法与27. 移除元素类似，同样使用快慢两个指针来对数组进行遍历。当快指针fast遇到0时保持慢指针不动，否则交换两个指针指向的元素并且移动慢指针slow。

题目链接：

python代码：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        slow, fast = 0, 0

        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1

C++代码：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0;

        for (int fast = 0; fast < nums.size(); ++fast) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                ++slow;
            }
        }

        for (int i = slow; i < nums.size(); ++i) {
            nums[i] = 0;
        }
    }
};

844. 比较含退格的字符串

给定s和t两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回true。#代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例 2：

输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

示例 3：

输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

1 <= s.length, t.length <= 200
s和t只含有小写字母以及字符#

Solution

利用双指针可以在O(1)的空间复杂度来解决这个题目。由于退格字符#不会影响到它后面的字符，我们可以从后向前对两个字符串进行遍历。具体来说我们使用i和j两个指针分别指向两个字符串的末尾，skipI和skipJ分别表示字符串中中遍历到的退格。算法整体思路如下：

如果字符串中当前的字符为#则向前移动i或者j，对应的skipI和skipJ需要进行自增。
如果字符串中当前的字符不是#，则根据skipI和skipJ是否为选择0继续向前移动或是停止。
比较两个字符串当前的最末位s[i]和t[j]，如果不相等则返回False，否则回到第1步继续进行比较。

题目链接：

python代码：

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        i, j = len(s)-1, len(t)-1
        skipI, skipJ = 0, 0

        while i >= 0 or j >= 0:
            ## back move i
            while i >= 0:
                if s[i] == "#":
                    i -= 1
                    skipI += 1
                else:
                    if skipI > 0:
                        i -= 1
                        skipI -= 1
                    else:
                        break
            
            ## back move j
            while j >= 0:
                if t[j] == "#":
                    j -= 1
                    skipJ += 1
                else:
                    if skipJ > 0:
                        j -= 1
                        skipJ -= 1
                    else:
                        break
            
            if i >= 0 and j >= 0:
                if s[i] != t[j]:
                    return False
            elif i >= 0 or j >= 0:
                return False
            
            i -= 1
            j -= 1
        
        return True

除此之外，也可以利用快慢指针来模拟字符串的退格过程。当快指针fast遇到非#字符时将它指向的元素赋给慢指针slow，然后将慢指针右移；否则将慢指针slow左移。遍历完成后慢指针slow前面的元素就都是退格后保存下的字符，我们只需要比较s和t经过退格后保存的字符是否一一对应相等即可。

使用这种方法需要额外注意一下python中不允许对str类型的数据进行修改，因此我们要把字符串先转换成List类型的数据。

python代码：

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def backspace(s: List[str]) -> List[str]:
            fast, slow = 0, 0
            for fast in range(len(s)):
                if s[fast] != "#":
                    s[slow] = s[fast]
                    slow += 1
                elif slow > 0:
                    slow -= 1
            
            return s[:slow]
        
        return backspace(list(s)) == backspace(list(t))

C++代码：

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        return removeBackSpace(s) == removeBackSpace(t);
    }

    string removeBackSpace(string s) {
        string ss;

        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != '#') {
                ss += s[i];
            } else if (!ss.empty()) {
                ss.pop_back();
            }
        }

        return ss;
    }
};

977.有序数组的平方

给你一个按非递减顺序排序的整数数组nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums已按非递减顺序排序

Solution

本题的直接解法是首先构造nums中元素平方构成的数组然后进行排序，此时的算法复杂度为O(n)+O(log n)。而利用双指针则只需要进行一次遍历即可：注意到nums数组平方的最大值一定在两端点，我们只需要利用left和right两个指针分别指向作业两端然后向中间进行遍历，每次选择平方较大的数将其赋给新数组的末尾即可。此时的算法复杂度为O(n)。

题目链接：

python代码：

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left, right = 0, len(nums)-1
        i = len(nums)-1
        ret = [-1]*len(nums)

        while left <= right:
            left2 = nums[left]*nums[left]
            right2= nums[right]*nums[right]

            if left2 < right2:
                ret[i] = right2
                right -= 1
            else:
                ret[i] = left2
                left += 1
            
            i -= 1
        
        return ret

C++代码：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int N = nums.size();

        auto res = vector<int>(N, 0);
        int i = 0, j = N-1, k = N-1;

        while (i <= j) {
            int i2 = nums[i] * nums[i];
            int j2 = nums[j] * nums[j];

            if (i2 < j2) {
                res[k] = j2;
                --j;
            } else {
                res[k] = i2;
                ++i;
            }
            
            --k;
        }

        return res;
    }
};

350. 两个数组的交集 II

给你两个整数数组nums1和nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致(如果出现次数不一致，则考虑取较小值)。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

Solution

本题的解法在于首先对两个数组进行排序，然后使用两个指针i和j对它们进行遍历：

如果nums1[i] == nums2[j]，则说明这个数字是两个数组的交集并将其添加到res中
如果nums1[i] != nums2[j]，则将数字较小的那个指针向后移动1位继续进行比较

当两个指针中有一个指向数组末尾时结束遍历，res中的数字即为两个数组的交集。

题目链接：

python代码：

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1 = sorted(nums1)
        nums2 = sorted(nums2)
        res = []

        i = j = 0

        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                res.append(nums2[j])
                i += 1
                j += 1

        return res

C++代码：

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        int N1 = nums1.size(), N2 = nums2.size();
        vector<int> res;

        int i = 0, j = 0;

        while (i < N1 && j < N2) {
            if (nums1[i] < nums2[j]) {
                ++i;
            } else if (nums1[i] > nums2[j]) {
                ++j;
            } else {
                res.push_back(nums1[i]);
                ++i;
                ++j;
            }
        }

        return res;
    }
};

滑动窗口

209. 长度最小的子数组

给定一个含有n个正整数的数组和一个正整数target。

找出该数组中满足其和≥ target的长度最小的连续子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 10⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Solution

本题的暴力解法是利用二重循环来构造所有可能的子列并计算子列之和，其算法复杂度为O(n²)。而利用双指针则可以构造一个滑动窗口[start, end]，同时利用变量s保存区间内元素之和。进行遍历时每次先向右移动end指针，然后右移left直到s小于target。右移left时每次减去nums[left]从而保证s等于区间内元素之和，同时需要更新满足s大于等于target条件的区间长度。

题目链接：

python代码：

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        start, end = 0, 0
        s = 0
        length = float("inf")

        for end in range(len(nums)):
            s += nums[end]
            while s >= target:
                length = min(length, end-start+1)
                s -= nums[start]
                start += 1
        
        return 0 if length == float("inf") else length

C++代码：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int N = nums.size();

        if (N == 0) return 0;

        int res = INT_MAX;
        int start = 0, sum = 0;

        for (int end = 0; end < N; ++end) {
            sum += nums[end];

            while (sum >= target) {
                res = min(res, end - start + 1);
                sum -= nums[start];
                
                ++start;
            }
        }

        return res == INT_MAX ? 0 : res;
    }
};

904. 水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组fruits表示，其中fruits[i]是第i棵树上的水果种类。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有两个篮子，并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上恰好摘一个水果。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组fruits，返回你可以收集的水果的最大数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：

1 <= fruits.length <= 10⁵
0 <= fruits[i] <= fruits.length

Solution

本题的解法是使用双指针构造滑动窗口[start, end]，同时使用哈希表bag来保存窗口中不同水果的个数。我们每次右移一下end指针，然后更新bag中的水果数量。如果bag中的键值超过2个，说明我们需要右移start指针直到键值为2。这里需要注意的是当bag中某个键值对应的记数为0时需要将该键值删除。

题目链接：

python代码：

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        start, end = 0, 0
        bag = {}
        length = 0

        for end, x in enumerate(fruits):
            bag[x] = bag.get(x, 0)+1

            while len(bag) > 2:
                bag[fruits[start]] -= 1

                if bag[fruits[start]] == 0:
                    bag.pop(fruits[start])
                
                start += 1

            length = max(length, end-start+1)

        return length

C++代码：

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int N = fruits.size();
        unordered_map<int, int> bag;

        int start = 0, res = 0;

        for (int end = 0; end < N; ++end) {
            ++bag[fruits[end]];

            while (bag.size() > 2) {
                auto it = bag.find(fruits[start]);
                --(it->second);

                if (it->second == 0) bag.erase(it);

                ++start;
            }

            res = max(res, end - start + 1);
        }

        return res;
    }
};

76. 最小覆盖子串

给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。

注意：

对于t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。
如果s中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3：

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

m == s.length
n == t.length
1 <= m, n <= 10⁵
s和t由英文字母组成

Solution

本题比常见的滑动窗口要更复杂一些。除了标准的start和end双指针外，我们还需要一个哈希表(字典)need来维护窗口中字符的数量，以及变量needCnt记录当前窗口还需要的字符数量。整个算法流程如下：

初始化字典need，使得字符串s中的字符对应0，t中每个字符自增1。
初始化needCnt为字符串t的长度。
每次向右移动一位end指针，并且把need中对应字符char的记数减1；如果char还在t中(need[char]>0)还需要令needCnt自减1。
当needCnt为0时说明当前窗口[start, end]已经包含了字符串t，此时我们要右移start指针直到它指向的元素s[start]在字典need中的记数为0，这表示窗口中不再有多余的字符。
如果[start, end]小于当前解ret则进行更新。
令need[s[start]]和needCnt自增1，并且右移一位start指针，然后进入end指针的下一轮循环。

上述流程还可以参考如下图示：

初始化相关变量。

右移end指针直到needCnt == 0，此时窗口[start, end]已经包含了字符串t。

不断右移start指针使得窗口[start, end]的起点没有多余的字符，然后更新当前解。

右移一位start指针，开始寻找下一个满足要求的滑动窗口。

题目链接：

python代码：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        start, end = 0, 0
        ret = (0, float("inf"))

        ## initialize need and needCnt
        need = {char: 0 for char in s}
        for char in t:
            need[char] = need.get(char, 0)+1
        
        needCnt = len(t)

        for end, char in enumerate(s):
            if need[char] > 0:
                needCnt -= 1
            
            need[char] -= 1

            ## if [start, end] includes t
            if needCnt == 0:
                ## right move start until s[start] in t
                while True:
                    if need[s[start]] == 0:
                        break
                    
                    need[s[start]] += 1
                    start += 1
                
                ## update current solution string
                if end-start < ret[1]-ret[0]:
                    ret = (start, end)
                
                ## right move start for the next iteration
                need[s[start]] += 1
                needCnt += 1
                start += 1
        
        return "" if ret[1] > len(s) else s[ret[0]:ret[1]+1]

其它

59. 螺旋矩阵 II

给你一个正整数n，生成一个包含1到n²所有元素，且元素按顺时针顺序螺旋排列的n x n正方形矩阵matrix。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 20

Solution

本题解法是由外向内逐层填入对应元素。在每一层上我们首先确定4条边界l、r、t、b，然后按照从左到右、从上到下、从右到左、从下到上的顺序填入元素e。每完成一条边后注意要更新下一轮的边界。

题目链接：

python代码：

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[0 for _ in range(n)] for _ in range(n)]

        l, r, t, b = 0, n - 1, 0, n - 1
        e, n2 = 1, n*n

        while e <= n2:
            ## top
            for i in range(l, r+1):
                matrix[t][i] = e
                e += 1
                
            t += 1
            
            ## right
            for i in range(t, b+1):
                matrix[i][r] = e
                e += 1
            
            r -= 1
            
            ## bottom
            for i in range(r, l-1, -1):
                matrix[b][i] = e
                e += 1
            
            b -= 1
            
            ## left
            for i in range(b, t-1, -1):
                matrix[i][l] = e
                e += 1
            
            l += 1
        
        return matrix

C++代码：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int n2 = n*n;

        vector<vector<int>> res(n, vector<int>(n, 0));
        int t = 0, b = n-1, l = 0, r = n-1;

        int num = 1;
        while (num <= n2) {
            // top
            for (int i=l; i <= r; ++i) {
                res[t][i] = num++;
            }
            ++t;

            // right
            for (int i=t; i <= b; ++i) {
                res[i][r] = num++;
            }
            --r;

            // bottom
            for (int i=r; i >= l; --i) {
                res[b][i] = num++;
            }
            --b;

            // left
            for (int i=b; i >= t; --i) {
                res[i][l] = num++;
            }
            ++l;
        }

        return res;
    }
};

54. 螺旋矩阵

给你一个m行n列的矩阵matrix，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

Solution

本题解法基本就是螺旋矩阵 II的逆过程，我们只需要对matrix每一层的4条边按顺序进行遍历即可。不过在对每条边遍历后需要额外检查一下是否已经完成了matrix所有元素的访问，如果完成了就及时退出从而防止访问越界。

题目链接：

python代码：

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        ret = [0 for _ in range(m*n)]

        l, r, t, b = 0, n-1, 0, m-1
        idx = 0
        mn = m*n

        while True:
            ## top
            for i in range(l, r+1):
                ret[idx] = matrix[t][i]
                idx += 1
            
            t += 1

            if idx == mn:
                break

            ## right
            for i in range(t, b+1):
                ret[idx] = matrix[i][r]
                idx += 1
            
            r -= 1
            
            if idx == mn:
                break

            ## bottom
            for i in range(r, l-1, -1):
                ret[idx] = matrix[b][i]
                idx += 1
            
            b -= 1

            if idx == mn:
                break

            ## left
            for i in range(b, t-1, -1):
                ret[idx] = matrix[i][l]
                idx += 1
            
            l += 1

            if idx == mn:
                break
        
        return ret

C++代码：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;

        int m = matrix.size();
        int n = matrix[0].size();

        int t = 0, r = n-1, b = m-1, l = 0;
        int mn= m*n, num=0;

        while (num <= mn) {
            // top
            for (int i=l; i <= r; ++i) {
                res.push_back(matrix[t][i]);
                ++num;
            }

            ++t;
            if (num == mn) break;

            // right
            for (int i=t; i <= b; ++i) {
                res.push_back(matrix[i][r]);
                ++num;
            }

            --r;
            if (num == mn) break;

            // bottom
            for (int i=r; i >= l; --i) {
                res.push_back(matrix[b][i]);
                ++num;
            }

            --b;
            if (num == mn) break;

            // left
            for (int i=b; i >= t; --i) {
                res.push_back(matrix[i][l]);
                ++num;
            }

            ++l;
            if (num == mn) break;
        }

        return res;
    }
};

189. 轮转数组

给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。

示例 1：

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2：

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
0 <= k <= 10⁵

Solution

如果允许使用额外的空间，我们只需要把nums的前k % len(nums)个元素放置到nums末尾即可。而如果不允许使用额外的空间则要复杂一些，此时需要对nums进行3次翻转：

将整个nums数组翻转
将nums的前k % len(nums)位翻转
将nums剩余的部分翻转

题目链接：

python代码：

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 % N
        
        if k == 0:
            return
        
        def reverse(i: int, j: int) -> None:
            nonlocal nums

            while i < j:
                nums[i], nums[j] = nums[j], nums[i]

                i += 1
                j -= 1
        
        reverse(0, N-1)
        reverse(0, k-1)
        reverse(k, N-1)

C++代码：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int N = nums.size();
        k = k % N;

        reverse(nums, 0, N-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, N-1);
    }

    void reverse(vector<int>& nums, int i, int j) {
        while (i < j) {
            swap(nums[i], nums[j]);

            ++i;
            --j;
        }
    }
};

48. 旋转图像

给定一个n × n的二维矩阵matrix表示一个图像。请你将图像顺时针旋转90度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

Solution

本题的解法分为两步。首先对matrix按照主对角线进行转置。

然后对转置后matrix的每一行进行翻转。

题目链接：

python代码：

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """

        N = len(matrix)

        for i in range(N):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        for line in matrix:
            line.reverse()

C++代码：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int N = matrix.size();

        for (int i=0; i < N; ++i) {
            for (int j=0; j < i; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        for (int i=0; i < N; ++i) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

而如果题目要求逆时针旋转90度也可以使用类似的方法，此时只需要在第一步转置时按照副对角线转置即可。

python代码：

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """

        N = len(matrix)

        for i in range(N):
            for j in range(N-i):
                matrix[i][j], matrix[N-j-1][N-i-1] = matrix[N-j-1][N-i-1], matrix[i][j]
        
        for line in matrix:
            line.reverse()

136. 只出现一次的数字

给你一个非空整数数组nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1：

输入：nums = [2,2,1]
输出：1

示例 2：

输入：nums = [4,1,2,1,2]
输出：4

示例 3：

输入：nums = [1]
输出：1

提示：

1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
除了某个元素只出现一次以外，其余每个元素均出现两次

Solution

本题的解法在于使用位运算。这里需要引入异或运算⊕的性质：

任何数和0进行异或运算等于自身，a ⊕ 0 = a
任何数和其自身进行异或运算等于0，a ⊕ a = 0
异或运算满足交换律和结合律

因此我们可以对nums中的所有元素都进行异或运算，最后就会得到只出现一次的数字。

题目链接：

python代码：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0

        for num in nums:
            res = res ^ num
        
        return res

C++代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;

        for (auto x: nums) res = res ^ x;

        return res;
    }
};

Reference

NEXT链表