阿里 | 阿里巴巴编程题（2星）

问题与解析

https://www.nowcoder.com/test/question/done?tid=55328459&qid=1664808#summary

1、完美对

alt alt

解析

两个数组a, b互为完美对的充分必要条件是：对于任意的i,j，有ai+bi=aj+bj
这等价于:ai-aj=-(bi-bj)
可以证明，上述命题等价于：
两个数组a, b互为完美对的充分必要条件是：对于任意不越界的i,i-1，有a[i]-a[i-1]= - {b[i]-b[i-1]}可以了。
容易观察得到两个元素是完美对，它们的K个属性的差分为相反数，差分之和也为相反数。
因此，用哈希法存储元素下标，用K个属性的差分之和作为哈希值。

答案

https://www.nowcoder.com/questionTerminal/f5a3b5ab02ed4202a8b54dfb76ad035e?answerType=1&f=discussion

package com.yyc.test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class Text1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[][] nums = new int[n][k];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                nums[i][j] = sc.nextInt();
            }
        }
        int res = 0;
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int key = nums[i][1] + nums[i][0];
            if (map.containsKey(key)) {
                ArrayList<Integer> rowList = map.get(key);//行号
                res += valEquals(rowList, i, nums);
                rowList.add(i);
                map.put(key, rowList);
            } else {
                ArrayList<Integer> rowList = new ArrayList<>();
                rowList.add(i);
                map.put(key, rowList);
            }
        }
        System.out.println(res);
    }

    //返回两个数组中，互为完美对的个数

    /**
     * @param rowList 行号集合
     * @param cur     当前行号
     * @param nums    原始数据
     * @return
     */
    public static int valEquals(ArrayList<Integer> rowList, int cur, int[][] nums) {
        int res = 0;
        int[] curVal = nums[cur];
        for (Integer row : rowList) {
            int[] rowVal = nums[row];
            boolean flag = true;
            for (int i = 1; i < curVal.length; i++) {
                if (curVal[i] + curVal[i - 1] == rowVal[i] + rowVal[i - 1]) {
                    continue;
                } else {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                res++;
            }
        }
        return res;
    }
}