利用Java和尺取法解决问题:数组里有n个元素,两两相减,有多少对相减的元素的绝对值小于k。编写完整代码并注释
时间: 2024-09-12 10:14:22 浏览: 56
在Java中,我们可以利用哈希表的数据结构来解决这个问题,通过遍历数组一次,统计每个数作为差值时出现的次数,然后检查哪些差值的绝对值小于给定的阈值k。以下是完整的Java代码示例:
```java
import java.util.HashMap;
import java.util.Map;
public class TwoSumSmallerThanK {
public int countPairs(int[] nums, int k) {
// 创建一个空的HashMap,键是数值,值是该数值作为差值出现的次数
Map<Integer, Integer> map = new HashMap<>();
// 遍历数组,对于每个元素num,更新它对应的计数
for (int num : nums) {
// 如果当前元素已经存在,将计数加一;如果不存在,则初始化为1
map.putIfAbsent(Math.abs(num), 0);
map.put(Math.abs(num), map.getOrDefault(Math.abs(num), 0) + 1);
// 检查num和-k之间的所有配对是否满足条件
if (map.containsKey(-k)) {
// 当前元素加上-k小于等于k,找到一对满足条件的配对
int count = map.getOrDefault(-k, 0);
int sum = num - (-k); // |num - (-k)| 就是差值
if (sum <= k) {
count--;
}
map.put(-k, count);
}
}
// 初始化结果,表示绝对值小于k的配对数量
int result = 0;
// 累加那些绝对值小于k的元素的计数
for (int count : map.values()) {
if (count > 0) {
result += count * (count - 1) / 2; // 对于正数,使用组合公式计算满足条件的配对数量
}
}
return result;
}
// 示例数组和阈值
public static void main(String[] args) {
TwoSumSmallerThanK solver = new TwoSumSmallerThanK();
int[] nums = {4, 2, 5, 7};
int k = 5;
System.out.println("Number of pairs with absolute difference smaller than " + k + ": " + solver.countPairs(nums, k));
}
}
```
阅读全文