找能构成1的分数对

哈希表

public int solution(int[] X, int[] Y) {
    int n = X.length;
    int mod = (int) 1e9 + 7;
    Map<String, Integer> map = new HashMap<>();
    long res = 0;
    for (int i = 0; i < n; i++) {
        int ai = X[i], bi = Y[i], k = gcd(ai, bi);
        if (k != 1) {
            X[i] /= k;
            Y[i] /= k;
        }
        // 找前面配对的数量，配对的分数是px / py
        int px = Y[i] - X[i], py = Y[i];
        k = gcd(px, py);
        if (k != 1) {
            px /= k;
            py /= k;
        }
        // key是target数，如果包含target那么就加上
        String key = String.valueOf(px) + "_" + String.valueOf(py);
        if (map.containsKey(key)) res = (res + map.get(key)) % mod;
        // System.out.println(key);
        // 写入当前的值
        key = String.valueOf(X[i]) + "_" + String.valueOf(Y[i]);
        map.put(key, map.getOrDefault(key, 0) + 1);
    }
    return (int) (res % mod);
}

public int gcd(int x, int y) {
    return y > 0 ? gcd(y, x % y) : x;
}

排序+双指针

class Pair implements Comparable<Pair> {
    int numerator;
    int denominator;

    public Pair(int numerator, int denominator) {
        int k = gcd(numerator, denominator);
        this.numerator = numerator / k;
        this.denominator = denominator / k;
    }

    @Override
    public int compareTo(Pair o) {
        double res = this.numerator / this.denominator - o.numerator / o.denominator;
        if (res > 0) {
            return 1;
        } else if (res == 0) {
            return 0;
        } else {
            return -1;
        }
    }
}

public int test(int[] X, int[] Y) {
    // write your code in Java SE 8
    int n = X.length;
    int mod = (int) 1e9 + 7;
    Pair[] pair = new Pair[n];
    for (int i = 0; i < n; i++) {
        pair[i] = new Pair(X[i], Y[i]);
    }
    Arrays.sort(pair);

    long res = 0;
    for (int i = 0; i < n; i++) {
        int l = i, r = n - 1;
        while (l < r) {
            if (pair[l].denominator != pair[r].denominator) {
                r--;
                continue;
            }
            long res1 = (long) pair[l].numerator + (long) pair[r].numerator;
            long res2 = (long) pair[l].denominator;
            if (res1 == res2) {
                res = (res + 1) % mod;
                r--;
            } else if (res1 < res2) {
                l++;
            } else {
                r--;
            }
        }
    }
    return (int) (res % mod);
}

赏

谢谢你请我吃糖果

微信