有界平方和算法

Question

问题如下：

You are given two arrays of integers a and b, and two integers lower and upper. 
Your task is to find the number of pairs (i, j) such that lower ≤ a[i] * a[i] + b[j] * b[j] ≤ upper.

Example:

For a = [3, -1, 9], b = [100, 5, -2], lower = 7, and upper = 99, the output should be boundedSquareSum(a, b, lower, upper) = 4.
There are only four pairs that satisfy the requirement:
If i = 0 and j = 1, then a[0] = 3, b[1] = 5, and 7 ≤ 3 * 3 + 5 * 5 = 9 + 25 = 36 ≤ 99.
If i = 0 and j = 2, then a[0] = 3, b[2] = -2, and 7 ≤ 3 * 3 + (-2) * (-2) = 9 + 4 = 13 ≤ 99.
If i = 1 and j = 1, then a[1] = -1, b[1] = 5, and 7 ≤ (-1) * (-1) + 5 * 5 = 1 + 25 = 26 ≤ 99.
If i = 2 and j = 2, then a[2] = 9, b[2] = -2, and 7 ≤ 9 * 9 + (-2) * (-2) = 81 + 4 = 85 ≤ 99.
For a = [1, 2, 3, -1, -2, -3], b = [10], lower = 0, and upper = 100, the output should be boundedSquareSum(a, b, lower, upper) = 0.
Since the array b contains only one element 10 and the array a does not contain 0, it is not possible to satisfy 0 ≤ a[i] * a[i] + 10 * 10 ≤ 100.

现在，我知道有一种蛮力方法可以解决这个问题，但是这个问题的最佳解决方案是什么？

Answer 1

使用元素的绝对值对较小的数组进行排序，然后对于未排序数组中的每个元素，二进制搜索已排序元素的区间。

Answer 2

当计算高于upper 限制时，您可以break 循环。我会减少执行时间。

function boundedSquareSum(a, b, lower, upper) {
    let result = 0; 
    a = a.sort((i,j) => Math.abs(i) - Math.abs(j));
    b = b.sort((i,j) => Math.abs(i) - Math.abs(j))
    
    
 
    for(let i = 0; i < a.length; i++) {
        let aValue = a[i] ** 2;
        
        if(aValue > upper) {
            break; // Don't need to check further
        }
        
        for(let j = 0; j < b.length; j++) {
            let bValue = b[j] ** 2;
            let total = aValue + bValue;
            
            if(total > upper) {
                break; // Don't need to check further
            }
            
            if((total >= lower && total <= upper) ) {
                result++;
            }
        }
    }
    
    
    return result;
}

有界平方和算法

Bounded square sum algorithm

algorithm

time-complexity