基础算法 - Ada Lovelemon

前缀和、双指针与滑动窗口

双指针#

双指针是一种基础算法，通常用于求解一维数组类问题。一般要求这类问题具有两个性质，单调有序性和双指针区间扫描。这类问题可以用双重循环求解，但时间复杂度为O(n^2)，而双指针的时间复杂度为O(n)。扫描的方向分为同向扫描和反向扫描两种。

同向扫描（快慢指针，滑动窗口）#

同向扫描是指两个指针从同一方向出发，分别以不同的速度向前移动。具体的移动情况视题目要求而定。定义滑动窗口为[i, j]（左闭右开符合程序员习惯），其中i和j分别表示窗口的左边界和右边界。while循环条件是j < n，即j指针不能超过数组的长度。

一般地，使用滑动窗口解题是考虑到问题对象为区间（子序列、字串等），且区间具有单调性，即对于某个相关的函数f(i, j)，i增大时f(i, j)的变化情况与j的变化情况相反，例如，i增大时，f(i, j)减小，j增大时f(i, j)增大。题目的要求就是找到f(i, j)符合某些条件的对应的区间。

Example Problem 统计满足 K 约束的子字符串数量

给你一个二进制字符串 s 和一个整数 k。

如果一个二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

字符串中 '0' 的数量最多为 k。字符串中 '1' 的数量最多为 k。返回一个整数，表示 s 的所有满足 k 约束的子字符串的数量

def countKConstraintSubstrings(s: str, k: int) -> int:
    # as because it's and, so we could use sliding window
    n = len(s)
    count = [0, 0]
    res = 0
    i = 0
    for j in range(n):  # window = s[i:j+1], len(window) = j + 1 - i
        count[int(s[j])] += 1
        while count[0] > k and count[1] > k:
            count[int(s[i])] -= 1
            i += 1
        res += j - i + 1    
        # 这里暗含了一点，就是如果长度为 j - i + 1的子字符串满足条件的话，
        # 那么减小窗口长度的长度更小的子字符串一定满足条件，从而不必要重复计算，
        # 可以直接加 j - i + 1，表示从j - i + 1到长度缩减为1的子串都满足条件（j - i + 1）个
    return res

Example Problem 数组去重

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

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。返回 k 。


def removeDuplicates(nums):
    if len(nums) == 0:
        return 0
    i = j = 1  # never from 0, because nums[0] is unique and i always point to next pos to fill
    while j < len(nums):
        if nums[j] != nums[j - 1]: # new land
            nums[i] = nums[j]
            i += 1
        j += 1  # j always ++
    return i

Example Problem 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

# 这是真快慢指针
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

def hasCycle(head: ListNode):
    if not head or not head.next:
        return False
    i, j = head, head.next
    while j and j.next:
        if i == j:
            return True
        i = i.next
        j = j.next.next
    return False

反向扫描（左右指针，双元素）#

反向扫描通常涉及两个元素的操作，而不是区间的操作。分别令左指针i指向0，右指针j指向n - 1，注意这里是n - 1，而不是n, 因为这里不需要左闭右开，他不是区间。while循环条件是i < j 或 i <= j。通常需要一维数组具有单调性。

Example Problem 两数之和 1

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回这两个整数。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。

def twoSum(nums, target):
    i, j = 0, len(nums) - 1
    nums.sort() # 需要单调性
    while i < j:    # 两数不同
        if nums[i] + nums[j] > target:
            j -= 1
        elif nums[i] + nums[j] < target:
            i += 1
        else:
            return [nums[i], nums[j]]
    return None

Example Problem 两数之和 2

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。

from collections import defaultdict

def twoSum(nums, target):
    hash_map = defaultdict(lambda : -1) # 必须用默认字典，需要记住默认字典的调用
    for i in range(len(nums)):
        if hash_map[target - nums[i]] != -1:    # 有对应的元素
            return [hash_map[target - nums[i]], i]
        hash_map[nums[i]] = i
    return None

两题的区别是，第一题是求和为target的两个数，第二题是求和为target的两个数的下标。所以第一题既可以用双指针，也可以用哈希表。第二题只能用哈希表。哈希表的时间复杂度是O(n)，空间复杂度是O(n)。反向扫描的时间复杂度是O(n)，空间复杂度是O(1)。

前缀和#

前缀和是一个常用的算法技巧，主要用于快速计算数组中某个区间的和。通过预处理一个前缀和数组，可以在O(1)的时间复杂度内计算任意区间的和。前缀和数组的定义如下：

\text{prefix}[i] = \sum_{j=0}^{i} \text{arr}[j]

其中，prefix[i]表示数组arr中从下标0到i的元素之和。

通常，前缀和数组的计算时间复杂度为O(n)，查询时间复杂度为O(1)。

int* prefix_sum(int* arr, int n) {
    int* prefix = new int[n + 1];
    prefix[0] = 0; // 前缀和数组的第一个元素为0
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + arr[i - 1]; // 计算前缀和
    }
    return prefix;
}

一般地，都会把prefix[0]设为0，这样可以方便地计算从下标1到i的元素之和。那么此时

prefix[i]表示从下标0到i - 1的元素之和，长度为i，计算的是arr[0]到arr[i - 1]的和
prefix[j] - prefix[i]表示从下标i到j - 1的元素之和，长度为j - i，计算的是arr[i]到arr[j - 1]的和
prefix[n] - prefix[i]表示从下标i到n - 1的元素之和，长度为n - i，计算的是arr[i]到arr[n - 1]的和

Example Problem 长度最小的数组

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

找出该数组中满足其总和大于等于 target 的长度最小的子数组 [nums_l, nums_l+1, ..., nums_r-1, nums_r] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

def prefix_sum(nums):
    prefix = [0] * (len(nums) + 1)
    cum_sum = 0
    for i, num in enumerate(nums):
        cum_sum += num
        prefix[i + 1] = (cum_sum)
    return prefix

def min_sub_array_len(target, nums):
    prefix = prefix_sum(nums)
    min_len = len(nums) + 1
    i, j = 0, 1 # 双指针同向遍历
    while j < len(prefix):
        if prefix[j] - prefix[i] >= target:
            min_len = min(min_len, j - i)   # 长度是 j - i
            i += 1
        else:
            j += 1

    return min_len if min_len != len(nums) + 1 else 0