关于周赛1498题的疑惑

Question

波波老师，周赛1498题我是利用排序+双指针，可是我总是在数组在32以下的都可以AC，但是数据量超过32就不行，我加了快速幂，但是还是不行，现在不知道怎么办了，波波老师，您可以帮我看看我的逻辑有错嘛，我已经困扰这个问题好几天了。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

class Solution {
    public int numSubseq(int[] nums, int target) {
        Arrays.sort(nums);
        int res = 0;
        int l = 0, r = nums.length - 1;
        //双指针，始终保持左边的数有效
        while (l <= r) {
            if (nums[l] + nums[r] > target) 
                r--;
            else {
                res = (int)((res + myPow(2, r - l)) % (1000000000 + 7));
                l++;
            }
        }
        return res;
    }
    //快速幂
    private long myPow(int x, int n){
        if(n == 0) return 1;
        long t = x;
        long res = 1;
        while(n > 0){
            if((n & 1) == 1)
                res *= t;
            t *= t;
            n >>= 1;
        }
        return res;
    }
}

Answer 1

liuyubobobo 2020-07-01 04:58:57

myPow 中的 res 和 t 是可能溢出的。 

改成下面的方式就 ok 了：

private long myPow(int x, int n){

    if(n == 0) return 1;
    long t = x;
    long res = 1;
    while(n > 0){
        if((n & 1) == 1)
            res = (res * t) % (1000000000 + 7);
        t = (t * t) % (1000000000 + 7);
        n >>= 1;
    }
    return res % (1000000000 + 7);
}

继续加油！：）

• 提问者 v不离不弃v #1

  波波老师，为啥leetcode50题数据量更大[-2^31, 2^31 - 1]为啥就不会溢出(返回值为double)，但是在这里才10^6次方就会溢出呢？我记得java中long和double的范围都是64bit呀？

• liuyubobobo 回复 提问者 v不离不弃v #2

  double 没有溢出的概念，只有精度不准确。但是 long 有。long 意味着 2^63 就溢出了。这个问题的 n 达到了 10^5。