题解 | #两个有序数组间相加和的Topk问题#

建立信息节点Node，存放两个数组中取用的下标和累加值。 建立大根堆，维护Node，按照累加值大到小存放。 使用HashSet维护Node的访问标记。

每次从堆中弹出Node时，取出两个数组中的下标位置，分别看看各自向前移动一个的累加和大小，形成新的节点，再入大根堆，直到满足弹出k个。

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;

public class Main {

    static class Node{
        int a,b,sum;
        Node(int a,int b,int sum){
            this.a = a;
            this.b = b;
            this.sum = sum;
        }
    }

    static int x(int a,int b,int cols){
        return a*cols + b;
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();

        int [] arr1 = new int[N], arr2 = new int[N];
        for(int i=0;i<N;i++) {
            arr1[i] = scanner.nextInt();
        }
        for(int i=0;i<N;i++){
            arr2[i] = scanner.nextInt();
        }

        PriorityQueue<Node> que = new PriorityQueue<Node>((o1,o2)->{ return o2.sum - o1.sum;});
        Set<Integer> isVisited = new HashSet<>();

        int cnt = 0;
        int [] ans = new int[Math.min(K,N*N)];
        int a = N-1,b = N - 1;
        que.add(new Node(a,b,arr1[a] + arr2[b]));
        isVisited.add(x(a,b,N));

        while(cnt < K){
            Node node = que.poll();
            ans[cnt++] = node.sum;
            a = node.a;
            b = node.b;
            isVisited.remove(x(a,b,N));
            if( a-1 >= 0 && !isVisited.contains(x(a-1,b,N)) ){
                isVisited.add(x(a-1,b,N));
                que.add(new Node(a-1,b,arr1[a-1] + arr2[b]));
            }
            if( b-1 >= 0 && !isVisited.contains(x(a,b-1,N)) ){
                isVisited.add(x(a,b-1,N));
                que.add(new Node(a,b-1,arr1[a] + arr2[b-1]));
            }
        }

        for(int i=0;i<cnt;i++){
            if(i!=0){
                System.out.print(" ");
            }
            System.out.print(ans[i]);
        }

    }

}