LeetCode 补充题 159. 有序数组中的目标和数对计数
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 167. 两数之和 II - 输入有序数组
:::
给定非降序整数数组
nums和目标值target，返回满足nums[i]+nums[j]=target且i<j的下标对数量。允许重复数，使用 64 位整数返回计数。
示例 1：
输入：
nums = [1,1,2,2,3], target = 4
输出：3
解释： 两个 1 分别与 3 配对，两个 2 组成另一对。
示例 2：
输入：
nums = [2,2,2,2], target = 4
输出：6
解释： 从四个位置选两个，共4×3/2=6对。
提示：
- 同一个位置不能重复使用。
- 数值相同但下标不同的配对分别计数。
题意分析
数组有序可以排除不可能配对的端点，但本题按下标计数，不能像只求一个答案那样找到后就返回，也不能先把重复值去掉。命中时需要一次算出重复段贡献。
解法：双指针与重复段计数
核心思路
[!blue]
若两端之和小于目标，左端与区间中其他更小的右值也不可能达标，可以移除左端；若大于目标，对称移除右端。这两种移动都不会漏掉合法数对。
和等于目标且两端值不同，设左端重复
p次、右端重复q次，每个左下标都能与每个右下标配对，贡献为p*q。处理后跳过两段，避免重复计数。若两端值相同，有序性保证剩余区间全是同一个值。直接从
t个位置选两个，贡献t*(t-1)/2，之后结束。循环条件left < right排除同一位置配对，和与计数都用 64 位计算。
解题步骤
- 和小则移动左端，和大则移动右端。
- 和相等且两端不同，统计两端重复段长度，贡献为两者乘积。
- 两端相等时剩余区间全相等，直接加组合数 n(n-1)/2。
代码实现
class Solution {
public long countPairs(int[] a, long target) {
int left = 0;
int right = a.length - 1;
long out = 0;
while (left < right) {
long sum = (long) a[left] + a[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else if (a[left] == a[right]) {
long n = right - left + 1L;
out += n * (n - 1) / 2;
break;
} else {
int x = a[left];
int y = a[right];
long p = 0;
long q = 0;
while (left <= right && a[left] == x) {
left++;
p++;
}
while (left <= right && a[right] == y) {
right--;
q++;
}
out += p * q;
}
}
return out;
}
}
func countPairs(a []int, target int64) int64 {
left, right := 0, len(a)-1
out := int64(0)
for left < right {
sum := int64(a[left]) + int64(a[right])
if sum < target {
left++
} else if sum > target {
right--
} else if a[left] == a[right] {
n := int64(right - left + 1)
out += n * (n - 1) / 2
break
} else {
x, y := a[left], a[right]
p, q := int64(0), int64(0)
for left <= right && a[left] == x {
left++
p++
}
for left <= right && a[right] == y {
right--
q++
}
out += p * q
}
}
return out
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
计数对象是下标对：两段之间做笛卡尔积，同一段内部取两个不同位置。
易错点总结
[!yellow]
不能对数值先去重，否则会丢掉不同下标的合法配对；计算和与组合数时都要避免 32 位溢出。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 167. 两数之和 II - 输入有序数组 | 中等 | 原题找到一对即返回，本题要统计所有下标对，命中后必须累计两端重复段的组合数。 |
| 15. 三数之和 | 中等 | 同样在有序区间内移动双指针，原题去重值组合，本题需要保留重复值对应的下标方案。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！