常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）

常用枚举技巧

枚举右，维护左

对于双变量问题，例如两数之和 $a_i+a_j=t$，可以枚举右边的 $a_j$，转换成单变量问题，也就是在 $a_i$ 左边查找是否有 $a_i=t-a_j$，这可以用哈希表维护。这个技巧叫做枚举右，维护左。

1
2
3
4
5
6
7
8


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        idx = {}
        for j, x in enumerate(nums):
            if target - x in idx:
                return [idx[target-x], j]
            idx[x] = j 
        