如何在数组中找到两个值相乘到某个数

Question

我想做的是搜索一个数组并找出是否有两个数字相乘为 225。这是我现在拥有的：

    int n = A.length;

    for(int i = 0; i >= n; i++){
        for(int j = 0; j >= n; j++){
            if(i == j){
            }
            else if(A[i] * A[j] == 225){
                return true;
            }
        }
    }
    return false;
}

发生的事情是它找到数组中的第一个值并将其与所有其他值相乘，一旦找到两个 225 的数字，那么它 returns 为真。我还做到了，如果 i 和 j 是相同的数字，那么它什么都不做，因为我不希望它比较同一位置的值。问题是即使在有两个乘以 225 的数字（如 15、45、60、15）的数组上，它也会继续返回 false。那么我的代码有什么问题。

Answer 1

for 循环有 1 个问题：

它应该是这样的：

int n = A.length;
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        if(i != j)
            if(A[i] * A[j] == 225)
                return true;

此外，您可以将此循环稍微优化为：

int n = A.length;
for(int i = 0; i < (n-1); i++)
    for(int j = (i+1); j < n; j++)
        if (A[i] * A[j] == 225)
            return true;

这里有一点不同的版本，平均复杂度为 O(N)：

    final Map<Integer, Boolean> set = new HashMap<>(A.length);
    for (final int i : A) {
        set.put(i, set.containsKey(i)); // store number from array, set to true if there are multiple occurrences of 2 numbers
    }
    for (final int i : A) {
        final int mult = 225 / i;
        if ((mult * i) == 225) { // test that integral multiplication leads to 225
            final Boolean m = set.get(mult);
            if (m != null) { // we have both numbers in set, now we should filter double counting
                if ((i != mult) || ((i == mult) && m.booleanValue()))
                    return true;
            }

        }
    }
    return false;

Answer 2

这里 Arrays.sort() 在内部使用快速排序

public class FindMultiplicationValueUsingpointer 
{
    private void operation(int [] arr, int required)
    {//2, 3, 4, 5, 6, 7
        Arrays.sort(arr);
        int right =arr.length-1;
        int left= 0, val;

            while(left<right)
            {
                System.out.println("left is "+arr[left]);
                System.out.println("right is "+arr[right]);
                val = arr[left]*arr[right];
                System.out.println("value is " +val);
                if(val<required)
                {
                    left = left+1;

                }
                else if(val>required)
                {
                    right=right-1;
                }

                else if(val==required)
                {
                    System.out.println("value matched");
                    break;

                }
            }   

    }

    public static void main(String[] args) 
    {
        int arr[] = {3, 2, 6, 7, 4, 5};
        int required = 20;
        FindMultiplicationValueUsingpointer  up = new FindMultiplicationValueUsingpointer();
        up.operation(arr, required);

    }

Answer 3

也可以使用 hashset 对任何数字进行一个 for 循环，这也将最小化迭代次数。最好的情况是 o(1)，最坏的情况是 o(n):

   public boolean  hasAnyPair(int[] arr, int n) {


        boolean hasPair=false;
        HashSet<Integer> set= new HashSet<Integer>();

        for(int i=0; i<arr.length; i++) {

            if(n>=arr[i] && n%arr[i]==0) {
                set.add(arr[i]);
                if(set.contains(n/arr[i])) {
                    hasPair=true;
                    break;
                }
            }

        }

        return hasPair;

    }

如何在数组中找到两个值相乘到某个数

How do I find two values in an array that multiply to a certain number

java

arrays

compare

numbers

multiplication