国密算法:SM2 / SM3 / SM4

国密算法是中国国家密码管理局发布的商用密码标准,在政府类、金融类网站中广泛使用。逆向时如果发现常规算法(AES/RSA/SHA)对不上,应优先考虑国密。 SM3 是中国国密哈希标准,结构类似 SHA-256,但使用完全不同的初始值、压缩函数和轮常数。 这 8 个值是 SM3 最核心的特征,出现在所有 SM3 实现中: 0x7380166F 是全网唯一的 SM3 特征常量,搜索它即可定位 SM3 实现。 代码中通常以循环左移的形式出现: 代码中出现 << 9 与 << 17 配对,或 << 15 与 << 23 配对,是 SM3 的次级特征。 在 Chro

分享

官方文档:https://www.oscca.gov.cn/sca/xwdt/2010-12/17/content_1002386.shtml
适用场景:逆向政府/金融类网站时识别和还原国密加密参数

国密算法是中国国家密码管理局发布的商用密码标准,在政府类、金融类网站中广泛使用。逆向时如果发现常规算法(AES/RSA/SHA)对不上,应优先考虑国密。


目录


SM3 哈希算法

SM3 是中国国密哈希标准,结构类似 SHA-256,但使用完全不同的初始值、压缩函数和轮常数。

算法特征

特征
输出长度 256 bit / 64 个十六进制字符
消息块大小 512 bit(64 字节)
轮数 64 轮
消息扩展 W[0..67] + W'[0..63],共 132 个字
压缩函数 8 个 32-bit 寄存器 A..H

魔法初始值(IV)

这 8 个值是 SM3 最核心的特征,出现在所有 SM3 实现中:

V0 = 0x7380166F
V1 = 0x4914B2B9
V2 = 0x172442D7
V3 = 0xDA8A0600
V4 = 0xA96F30BC
V5 = 0x163138AA
V6 = 0xE38DEE4D
V7 = 0xB0FB0E4E

0x7380166F 是全网唯一的 SM3 特征常量,搜索它即可定位 SM3 实现。

轮常数 T

T_j = 0x79CC4519  (j = 0..15,前 16 轮)
T_j = 0x7A879D8A  (j = 16..63,后 48 轮)

代码中通常以循环左移的形式出现:

// 常见写法
var T = [0x79CC4519, 0x7A879D8A];
// 或展开为 64 个预计算值

置换函数 P0 / P1

P0(X) = X ^ ROL(X, 9)  ^ ROL(X, 17)   // 压缩函数中使用
P1(X) = X ^ ROL(X, 15) ^ ROL(X, 23)   // 消息扩展中使用

代码中出现 << 9<< 17 配对,或 << 15<< 23 配对,是 SM3 的次级特征。

逆向识别方法

在 Chrome DevTools Sources 面板按 Ctrl+Shift+F 全局搜索以下任意一个常量:

搜索目标 说明
0x7380166f SM3 初始 IV 第一个,最有效
7380166f 不带前缀的十六进制字符串形式
0x79CC4519 SM3 轮常数 T(前 16 轮)
0x7A879D8A SM3 轮常数 T(后 48 轮)
sm3 库名关键字(sm-crypto、sm3 npm 包)

JS 实现

使用 sm-crypto 库

npm install sm-crypto
const { sm3 } = require('sm-crypto');

// 输入字符串,返回 64 位十六进制字符串
const hash = sm3('hello world');
console.log(hash); // 44f0061e69fa6fdfc290c494654a05dc0c053da7e5c52b84ef93a9d67d3fff88

// 输入字节数组
const hash2 = sm3([0x61, 0x62, 0x63]); // 'abc' 的字节

使用 sm3 npm 包

npm install sm3
const sm3 = require('sm3');

const hash = sm3('hello');

Python 实现

pip install gmssl
from gmssl.sm3 import sm3_hash
from gmssl import func

def sm3_digest(message: str) -> str:
    """SM3 哈希,输入字符串,返回 64 位十六进制"""
    msg_bytes = message.encode('utf-8')
    # gmssl 要求输入为整数列表
    msg_list = [b for b in msg_bytes]
    return sm3_hash(msg_list)

def sm3_digest_bytes(data: bytes) -> str:
    """SM3 哈希,输入字节,返回 64 位十六进制"""
    return sm3_hash(list(data))

# 使用示例
print(sm3_digest('hello world'))

SM4 对称加密

SM4 是中国国密分组密码标准,128 bit 密钥,16 字节块大小,32 轮 Feistel 结构,类似 AES-128,但使用完全不同的 S-Box 和轮结构。

算法特征

特征
密钥长度 128 bit(16 字节,固定)
块大小 128 bit(16 字节)
轮数 32 轮
工作模式 ECB / CBC(与 AES 相同概念)
填充方式 PKCS#7(最常见)、ZeroPadding

FK 常量(密钥扩展初始值)

FK[0] = 0xA3B1BAC6
FK[1] = 0x56AA3350
FK[2] = 0x677D9197
FK[3] = 0xB27022DC

0xA3B1BAC6 是 SM4 最核心的特征常量。

CK 常量(轮密钥生成,32 个)

CK[0]  = 0x00070E15   CK[8]  = 0xE0E7EEF5
CK[1]  = 0x1C232A31   CK[9]  = 0xFC030A11
CK[2]  = 0x383F464D   CK[10] = 0x181F262D
CK[3]  = 0x545B6269   CK[11] = 0x343B4249
CK[4]  = 0x70777E85   CK[12] = 0x50575E65
CK[5]  = 0x8C939AA1   CK[13] = 0x6C737A81
CK[6]  = 0xA8AFB6BD   CK[14] = 0x888F969D
CK[7]  = 0xC4CBD2D9   CK[15] = 0xA4ABB2B9

S-Box 特征(前 16 字节)

SM4 的 S-Box 与 AES 完全不同:

0xD6, 0x90, 0xE9, 0xFE, 0xCC, 0xE1, 0x3D, 0xB7,
0x16, 0xB6, 0x14, 0xC2, 0x28, 0xFB, 0x2C, 0x05

代码中出现 0xD6, 0x90, 0xE9 开头的 256 字节数组,即为 SM4 S-Box。

逆向识别方法

搜索目标 说明
0xA3B1BAC6 SM4 FK 常量,最有效
0xD6, 0x90, 0xE9 SM4 S-Box 开头
0x00070E15 CK 常量第一个
sm4 库名关键字
sm-crypto 常用 JS 库名

工作模式说明

模式 特点 逆向注意事项
ECB 无 IV,相同明文产生相同密文 逆向最简单,只需密钥
CBC 需要 IV(16 字节),链式加密 需同时确认 IV 来源

JS 实现

sm-crypto 库用法

npm install sm-crypto
const { sm4 } = require('sm-crypto');

// ── ECB 模式 ──────────────────────────────────────────────────

const key = '0123456789abcdeffedcba9876543210'; // 32 个十六进制字符 = 16 字节

// 加密(返回十六进制字符串)
const ciphertext = sm4.encrypt('hello world', key);

// 解密
const plaintext = sm4.decrypt(ciphertext, key);

// ── CBC 模式 ──────────────────────────────────────────────────

const iv = '0000000000000000'; // 32 个十六进制字符 = 16 字节

const cipherCBC = sm4.encrypt('hello world', key, {
    mode: 'cbc',
    iv: iv
});

const plainCBC = sm4.decrypt(cipherCBC, key, {
    mode: 'cbc',
    iv: iv
});

// ── 输出格式控制 ──────────────────────────────────────────────

// 默认输出十六进制,可改为 base64(部分版本支持)
const cipherHex = sm4.encrypt('hello', key, { mode: 'ecb', output: 'array' });

sm-crypto sm4.encrypt / sm4.decrypt 参数说明:

参数 类型 默认值 说明
msg string / Array 必填 明文或密文(解密时为十六进制字符串)
key string 必填 32 个十六进制字符(16 字节密钥)
options.mode string 'ecb' 工作模式,'ecb''cbc'
options.iv string undefined CBC 模式必填,32 个十六进制字符
options.output string 'string' 'string'(十六进制)或 'array'(字节数组)
options.pad boolean true 是否使用 PKCS#7 填充

Python 实现

from gmssl.sm4 import CryptSM4, SM4_ENCRYPT, SM4_DECRYPT
import base64

def sm4_ecb_encrypt(plaintext: str, key: str) -> str:
    """SM4-ECB 加密,返回十六进制字符串"""
    sm4 = CryptSM4()
    sm4.set_key(key.encode('utf-8'), SM4_ENCRYPT)
    encrypted = sm4.crypt_ecb(plaintext.encode('utf-8'))
    return encrypted.hex()

def sm4_ecb_decrypt(ciphertext_hex: str, key: str) -> str:
    """SM4-ECB 解密,输入十六进制字符串"""
    sm4 = CryptSM4()
    sm4.set_key(key.encode('utf-8'), SM4_DECRYPT)
    decrypted = sm4.crypt_ecb(bytes.fromhex(ciphertext_hex))
    # 去除 PKCS#7 填充
    pad_len = decrypted[-1]
    return decrypted[:-pad_len].decode('utf-8')

def sm4_cbc_encrypt(plaintext: str, key: str, iv: str) -> str:
    """SM4-CBC 加密,返回十六进制字符串"""
    sm4 = CryptSM4()
    sm4.set_key(key.encode('utf-8'), SM4_ENCRYPT)
    encrypted = sm4.crypt_cbc(iv.encode('utf-8'), plaintext.encode('utf-8'))
    return encrypted.hex()

def sm4_cbc_decrypt(ciphertext_hex: str, key: str, iv: str) -> str:
    """SM4-CBC 解密,输入十六进制字符串"""
    sm4 = CryptSM4()
    sm4.set_key(key.encode('utf-8'), SM4_DECRYPT)
    decrypted = sm4.crypt_cbc(iv.encode('utf-8'), bytes.fromhex(ciphertext_hex))
    pad_len = decrypted[-1]
    return decrypted[:-pad_len].decode('utf-8')

完整还原模板

从 JS 中扣出 SM4 代码后,使用以下 Python 模板对接:

from gmssl.sm4 import CryptSM4, SM4_ENCRYPT, SM4_DECRYPT

class SM4Helper:
    """SM4 加解密封装,对应 sm-crypto 库的默认行为"""

    def __init__(self, key: str, iv: str = None, mode: str = 'ecb'):
        """
        key : 16 字节字符串,或 32 个十六进制字符
        iv  : CBC 模式必填,16 字节字符串,或 32 个十六进制字符
        mode: 'ecb' 或 'cbc'
        """
        self.key = key.encode() if len(key) == 16 else bytes.fromhex(key)
        self.iv  = (iv.encode() if len(iv) == 16 else bytes.fromhex(iv)) if iv else None
        self.mode = mode

    def encrypt(self, plaintext: str) -> str:
        data = plaintext.encode('utf-8')
        # PKCS#7 手动填充(gmssl 的 crypt_ecb 不自动填充)
        pad_len = 16 - (len(data) % 16)
        data += bytes([pad_len] * pad_len)
        sm4 = CryptSM4()
        sm4.set_key(self.key, SM4_ENCRYPT)
        if self.mode == 'cbc':
            return sm4.crypt_cbc(self.iv, data).hex()
        return sm4.crypt_ecb(data).hex()

    def decrypt(self, ciphertext_hex: str) -> str:
        raw = bytes.fromhex(ciphertext_hex)
        sm4 = CryptSM4()
        sm4.set_key(self.key, SM4_DECRYPT)
        if self.mode == 'cbc':
            decrypted = sm4.crypt_cbc(self.iv, raw)
        else:
            decrypted = sm4.crypt_ecb(raw)
        pad_len = decrypted[-1]
        return decrypted[:-pad_len].decode('utf-8')


# 使用示例
helper = SM4Helper(key='0123456789abcdef', mode='ecb')
ct = helper.encrypt('hello world 1234')
print(ct)
print(helper.decrypt(ct))

SM2 非对称加密

SM2 是中国国密非对称加密标准,基于椭圆曲线密码学(ECC),功能类似 ECC/RSA,但使用国标椭圆曲线参数。

椭圆曲线参数(SM2 国标曲线)

p  = FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF
a  = FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC
b  = 28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93
n  = FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
Gx = 32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7
Gy = BC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0

这组参数是 SM2 唯一的识别特征,代码中任意出现一个都可确认是 SM2。

最常用于搜索的字符串:FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF(即 p 值)。

密文格式(关键逆向坑)

SM2 加密输出的密文有两种格式,国内网站的坑主要在这里:

格式 结构 说明
C1C3C2 公钥点 + 哈希 + 密文数据 GB/T 32918.4-2016 旧标准,国内老系统常见
C1C2C3 公钥点 + 密文数据 + 哈希 早期实现,部分库默认

C1 = 64 字节椭圆曲线点(未压缩)或 33 字节(压缩格式)
C3 = 32 字节(SM3 哈希)
C2 = 与明文等长的密文数据

实际密文前通常还有 1 字节前缀:

  • 04:未压缩点格式
  • 0203:压缩点格式

如果解密失败,优先尝试交换 C1C3C2 / C1C2C3 格式。

公钥 / 私钥格式

# 公钥:64 字节(未压缩),通常以 04 开头,共 65 字节十六进制 = 130 个字符
publicKey = '04' + x_hex + y_hex   # 128 + 2 = 130 字符

# 私钥:32 字节,64 个十六进制字符
privateKey = 'd4de15474db74d06491c440d305e012400990f3e390c7e87153c12db2ea60bb7'

公钥加密 / 私钥解密

JS 实现(sm-crypto)

npm install sm-crypto
const { sm2 } = require('sm-crypto');

// 密钥对生成(逆向时通常不需要,直接从源码提取公钥)
const keypair = sm2.generateKeyPairHex();
const publicKey  = keypair.publicKey;   // 130 字符十六进制
const privateKey = keypair.privateKey;  // 64 字符十六进制

// ── 加密 ──────────────────────────────────────────────────────

// cipherMode: 1 = C1C3C2(推荐,新标准),0 = C1C2C3(旧标准)
const ciphertext = sm2.doEncrypt('hello world', publicKey, 1);

// ── 解密 ──────────────────────────────────────────────────────

const plaintext = sm2.doDecrypt(ciphertext, privateKey, 1);

sm2.doEncrypt / doDecrypt 参数说明:

参数 类型 说明
msg string 明文(doEncrypt)或密文十六进制(doDecrypt)
key string 公钥十六进制(加密)或私钥十六进制(解密)
cipherMode number 1 = C1C3C2(新标准),0 = C1C2C3(旧标准)

签名 / 验签

const { sm2 } = require('sm-crypto');

// 签名(返回十六进制字符串)
const sigValue = sm2.doSignature('message to sign', privateKey);

// 验签
const result = sm2.doVerifySignature('message to sign', sigValue, publicKey);
// result: true / false

sm2.doSignature 参数说明:

参数 类型 默认值 说明
msg string 必填 待签名的消息
privateKey string 必填 私钥十六进制
options.hash boolean false 是否对消息先做 SM3 哈希
options.der boolean false 签名是否输出 DER 格式(某些服务端要求)
options.userId string '' 用户 ID,影响签名预处理(Z 值计算)

Python 实现(gmssl)

from gmssl.sm2 import CryptSM2

# 从逆向目标源码中提取到的密钥
public_key  = 'B9A4F11464885B6C....'  # 128 字符(不含 04 前缀)
private_key = 'd4de15474db74d06...'   # 64 字符

sm2_crypt = CryptSM2(
    public_key=public_key,
    private_key=private_key
)

# 加密(输出十六进制,C1C3C2 格式)
ciphertext = sm2_crypt.encrypt('hello world'.encode('utf-8'))
print(ciphertext.hex())

# 解密
plaintext = sm2_crypt.decrypt(ciphertext)
print(plaintext.decode('utf-8'))

# 签名
random_hex_str = 'f' * 64  # 实际应用中应使用随机数
signature = sm2_crypt.sign('message'.encode('utf-8'), random_hex_str)

# 验签
result = sm2_crypt.verify(signature, 'message'.encode('utf-8'))

逆向实战

判断是国密还是国际算法

优先通过以下步骤判断:

  1. 在 Sources 面板全局搜索 sm2 / sm3 / sm4 / sm-crypto,命中即为国密
  2. 搜索 0x7380166f(SM3 IV),命中即为 SM3
  3. 搜索 0xA3B1BAC6(SM4 FK),命中即为 SM4
  4. 搜索 FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF(SM2 曲线 p),命中即为 SM2
  5. 输出长度为 64 字符十六进制 → 可能是 SM3 或 SHA-256,用 IV 区分
  6. 看网站性质:政府(.gov.cn)、银行、金融系统 → 优先怀疑国密

特征常量速查表

算法 最有效搜索目标 次选
SM3 0x7380166f 0x79CC45190x7A879D8A
SM4 0xA3B1BAC6 0xD6,0x90,0xE9(S-Box 前缀)
SM2 FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF 32C4AE2C

常见国密使用场景

场景 通常算法 说明
登录密码加密 SM2 或 SM4 SM2 公钥加密密码明文,SM4 加密表单数据
接口请求签名 SM3 + SM2 SM3 哈希消息,SM2 私钥签名
数据传输加密 SM4-CBC 类似 AES-CBC,密钥通过 SM2 交换
Token / Session SM3 服务端用 SM3 生成 HMAC 风格 Token
政府业务系统 全套 SM2+SM3+SM4 国密 SSL(TLCP)协议,整套国密

Python 完整还原模板

以登录接口为例,SM2 加密密码:

import requests
from gmssl.sm2 import CryptSM2

# 第一步:从目标 JS 源码中提取公钥
# 搜索 publicKey、pubKey、sm2Key 等变量名
PUBLIC_KEY = '从JS源码中提取的128字符公钥(不含04前缀)'

def sm2_encrypt_password(password: str) -> str:
    """用网站公钥加密密码,还原 JS 端加密逻辑"""
    sm2 = CryptSM2(public_key=PUBLIC_KEY, private_key='')
    # 注意:gmssl 默认 C1C3C2,若网站用 C1C2C3 需要手动调整字节顺序
    encrypted = sm2.encrypt(password.encode('utf-8'))
    # 输出格式通常是 04 + hex,具体看网站抓包对比
    return '04' + encrypted.hex()

def login(username: str, password: str) -> dict:
    encrypted_pwd = sm2_encrypt_password(password)
    resp = requests.post(
        'https://example.gov.cn/api/login',
        json={'username': username, 'password': encrypted_pwd}
    )
    return resp.json()

踩坑与注意事项

SM2 密文格式混用:最常见的坑。抓包后若解密报错,先确认网站使用的是 C1C3C2 还是 C1C2C3,用 sm-crypto 的 cipherMode 参数控制(1 = C1C3C2,0 = C1C2C3)。

SM2 公钥前缀:JS 代码中的公钥有时含 04 前缀,有时不含。传给 Python gmsslpublic_key 不应包含 04 前缀;sm-crypto JS 库通常包含 04

SM4 密钥/IV 编码:密钥可能以十六进制字符串(32 字符)或原始字节(16 字节)形式传入,混淆时注意区分。

gmssl 版本:pip 上 gmssl 存在多个版本,API 差异较大,推荐指定 pip install gmssl==0.2.2 或最新稳定版,并查看当前版本的实际 API。

SM3 与 SHA-256 输出相同长度:两者都输出 64 字符十六进制,无法仅凭长度区分,必须通过常量值或库名判断。


最佳实践

优先搜索 sm-cryptogmsslsmCrypto 关键词:这三个是 JS 生态最常见的国密库;其次搜索 SM2 曲线参数前缀 FFFFFFFEFFFFFFFF,SM4 S-Box 首值 d6(十进制 214)。

SM4 与 AES 混淆时看块大小和密钥长度:SM4 和 AES-128 块大小相同(16 字节),密钥均 16 字节;区别在于 S-Box 不同,0xd6 是 SM4 S-Box 第一个值,而 AES 是 0x63

SM2 解密时先确认密文格式再写 Python:新国标(2012)是 C1C3C2,老标准(2010)是 C1C2C3;Python gmsslSM2.decrypt() 默认 C1C3C2,若网站用老标准需手动调换 C2 C3 顺序。

SM3 的 Python 还原用 gmssl.SM3gmssl.sm3.sm3_hash([v for v in data]) 接受字节列表,输出 64 字符十六进制;比 hashlib 更清晰,不需要手动实现。

遇到国密+AES 混合使用:部分网站用 SM2 加密 AES 密钥(类似 RSA+AES),先解出 SM2 密文获得 AES 密钥,再用 AES 解密正文。分层逐步还原。


常见陷阱

陷阱:SM2 公钥去掉/保留 04 前缀导致解密失败

现象: Python gmssl 用抓取的公钥解密抛异常或结果错误。
原因: SM2 公钥的非压缩格式以 04 开头(标志未压缩),gmsslSM2 类内部会自动处理;若传入时含 04 且库也加 04,会导致公钥错误。
解决: 检查 gmssl 当前版本 API 是否需要 04 前缀;通常传入 64 字节(128 字符)裸公钥(去掉 04)。

陷阱:SM4 的密钥和 IV 用字符串传入但库期望字节

现象: SM4 解密结果是乱码或报参数错误。
原因: JS 侧密钥是十六进制字符串(32 字符),但 Python 需要 16 字节;直接将字符串传入库等于把字符串的 UTF-8 字节当密钥。
解决: Python 侧 key = bytes.fromhex(hex_key);IV 同理。

陷阱:SM3-HMAC 与纯 SM3 混淆

现象: 同样输入用纯 SM3 计算结果不对,以为实现有差异。
原因: 代码实际使用了 SM3-HMAC(带密钥),签名结果包含密钥信息,纯 SM3 无法复现。
解决: 搜索是否有密钥参数传入 SM3 函数;Python 用 gmssl.sm3.sm3_hmac(key_bytes, data_bytes) 对应。


参见

魔法数字速查
RSA
Base64与编码
代码片段大全

阅读更多

Web 安全基础

1. HTML 转义(服务端渲染必须): 2. CSP(Content Security Policy): 3. HttpOnly Cookie:防止 JS 读取会话 Cookie: 4. 前端框架防护: 攻击者在第三方网站构造一个表单,诱导已登录用户提交,浏览器会自动携带目标站的 Cookie。 触发条件: 1. 用户已登录目标网站(Cookie 有效) 2. 目标 API 仅凭 Cookie 识别用户身份 3. 请求来源未验证 1. CSRF Token(推荐): 2. SameSite Cookie: 3. 验证 Origin/Referer 头:

By yellowdog

HTTP 协议深度指南

HTTP(HyperText Transfer Protocol)是 Web 的基础传输协议,基于 TCP/IP,采用请求/响应模型。 相关文档:Web安全基础(/web-an-quan-ji-chu/) FastAPI完全指南(/fastapi-wan-quan-zhi-nan/) Nginx完全指南(/nginx-wan-quan-zhi-nan/) 幂等性:多次执行相同请求,服务器状态结果相同。PUT /users/1 多次执行结果一致;POST /users 每次创建新资源,非幂等。 浏览器直接从本地缓存读取,不向服务器发送请求。 缓存命中时,状

By yellowdog

系统设计基础

SLA 对照表: 选择建议:无状态服务(Web 层、API 层)优先水平扩展;数据库初期垂直扩展,达到瓶颈后考虑分库分表或读写分离。 缓存穿透(查询不存在的 key,每次都打到 DB): 缓存击穿(热点 key 过期,瞬间大量请求打到 DB): 缓存雪崩(大量 key 同时过期,或缓存服务宕机): 令牌桶 Python 实现: Redis 实现分布式限流(滑动窗口): URL 命名规则: Cursor 分页响应格式: 雪花算法结构(64 bit): 定义:分布式系统不能同时满足以下三个特性: 在分布式环境中 P 是必须保证的,所以实际是 CP vs AP

By yellowdog

算法思路与模板

二分查找要求序列有序,每次将搜索范围缩减一半,时间复杂度 O(log n)。 两个指针从两端向中间收缩,常用于有序数组。 滑动窗口维护一个满足条件的区间 left, right,right 不断向右扩张,条件不满足时收缩 left。 滑动窗口通用框架: 1. 确定"子问题":原问题可以分解为哪些规模更小的同类问题 2. 定义 dpi 或 dpij 的含义,要足够清晰 3. 推导状态转移方程 4. 确定初始状态(边界条件) 5. 确定计算顺序(确保依赖的子问题先计算) 每件物品最多选一次。dpj = 容量为 j 时的最大价值,逆序遍历容量防止重复选取。 每

By yellowdog