如何在数组中找到两个乘以某个数字的值

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的数字，它就返回true。我也这样做，如果我和j是相同的数字，那么它什么也不做，因为我不希望它比较相同位置的值。问题是，即使在阵列上也会继续返回false，而阵列中有两个数字乘以225（如15,45,60,15）。那我的代码有什么问题。

Answer 1

你有一个for循环的问题：

它应该是这样的：

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（）在内部使用quicksort

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;

    }