方法思路

要找出满足a[i] + a[j] = k的(i, j)对数量，我们可以使用哈希表优化查找过程。题目说明i和j可以相等，这意味着我们需要考虑自身与自身配对的情况。

具体步骤：

1. 首先统计数组中每个元素的出现次数，存储在哈希表中
2. 遍历数组，对于每个元素a[i]：
   • 如果2*a[i]=k（即a[i]=k/2），则这个元素可以与自身配对
   • 否则，查找哈希表中k-a[i]的出现次数，这就是能与当前元素配对的元素数量
3. 累加所有可能的配对数量

代码实现

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用BufferedReader代替Scanner提高输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        System.out.println(countPairs(arr, k));
    }
    
    public static int countPairs(int[] arr, int k) {
        int count = 0;
        Map<Integer, Integer> freq = new HashMap<>();
        
        for (int num : arr) {
            int complement = k - num;
            
            // If we've seen the complement before, add those pairs
            if (freq.containsKey(complement)) {
                count += freq.get(complement) * 2;
            }
            
            // If the number is half of k, add one more pair (with itself)
            if (num * 2 == k) {
                count += 1;
            }
            
            // Update frequency
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        return count;
    }
}

Python

def count_pairs(arr, k):
    count = 0
    freq = {}
    
    for num in arr:
        complement = k - num
        
        # If we've seen the complement before, add those pairs
        if complement in freq:
            count += freq[complement] * 2
        
        # If the number is half of k, add one more pair (with itself)
        if num * 2 == k:
            count += 1
        
        # Update frequency
        freq[num] = freq.get(num, 0) + 1
    
    return count

# 读取输入
n, k = map(int, input().split())
arr = list(map(int, input().split()))

# 输出结果
print(count_pairs(arr, k))

C++

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int countPairs(vector<int>& arr, int k) {
    int count = 0;
    unordered_map<int, int> freq;
    
    for (int num : arr) {
        int complement = k - num;
        
        // If we've seen the complement before, add those pairs
        if (freq.find(complement) != freq.end()) {
            count += freq[complement] * 2;
        }
        
        // If the number is half of k, add one more pair (with itself)
        if (num * 2 == k) {
            count += 1;
        }
        
        // Update frequency
        freq[num]++;
    }
    
    return count;
}

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    cout << countPairs(arr, k) << endl;
    
    return 0;
}