会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
核心思路
质量互不相同，因此每个下标至多出现在一对 (u,v) 中。从左到右扫描数组，用哈希表记下已经出现过的质量及其下标。扫到下标 i 时，若 g−wi 曾出现在某个更早的下标 j，则 (j,i) 就是一对合法配对。由于 j 一定小于 i，自然满足 u<v。扫完后按 u 升序排序即可。
注意两点：先查表再把当前质量写入哈希表，这样 2wi=g 时不会把一件货和自己配对；配对完成的先后顺序是按较晚下标 v 出现的次序，不一定按 u 有序，必须再排一次。
也可以先按下标按质量排序，再双指针从两端向中间收。和为 g 时记录原下标（先换成 u<v），和偏小则左指针右移，和偏大则右指针左移。质量互不相同，指针各走一次即可。最后同样按 u 排序。两种做法复杂度同阶，下面代码采用哈希表。
