-1

我有一个代码作业，它在一个总和等于 k ​​的数组中搜索四个数字（在这个例子中，k = 10）。相同的数组元素可以多次使用。换句话说，它将数组的四个元素相加，将和与值 k 进行比较，如果相等则返回 true，否则移动到其他元素。到目前为止，代码将数组的四个不同元素相加，但我需要对其进行更改，以便在四个元素的总和中多次使用任何单个元素时它也可以工作，例如如果 array[2] * 4 == k 或 array[0] * 2 + array[1] * 2 == k，它返回 true。

代码中的“static int[][] esim”是示例输入。例如，{1, 2, 3, 4} 返回 true，因为当 k = 10 时 1 + 2 + 3 + 4 == k。{4, 3, 1, 5, 5, 6, 6} 在 true 时返回 false是预期的，因为代码没有考虑重复的元素，因此忽略了 2 * 4 + 2 * 1 == k。类似地，当期望为 true 时，{2, 3} 返回 false，尽管 2 * 2 + 2 * 3 == k。

任何人都可以给我一个提示如何实现我想要的？

import java.util.Arrays;

public class Etsinta2 {

    public static boolean etsi(int[] tl, int k) {
        Arrays.sort(tl);
        for (int i = 0; i < tl.length; i++) {
            int b = i + 1;
            int c = i + 2;
            int d = tl.length - 1;
            while (b < d) {
                if (tl[i] + tl[b] + tl[c] + tl[d] == k) {
                    return true;
                } else if (tl[i] + tl[b] + tl[c] + tl[d] < k) {
                    b++;
                    c++;
                } else {
                    d--;
                }
            }
        }
        return false;
    }

    static int[][] esim = new int[][]{{5},
        {2, 3},
        {1, 1, 1, 1},
        {1, 2, 3, 4},
        {4, 2, 3, 1},
        {4, 6, 5, 5},
        {6, 4, 5, 5},
        {6, 6, 6, 4},
        {4, 4, 1, 1, 1, 6, 6},
        {9, 1, 1, 1, 1, 5, 6},
        {4, 3, 1, 5, 5, 6, 6}};

    public static void main(String[] args) {
        for (int[] taulu : esim) {
            System.out.println(Arrays.toString(taulu) + " 10 : " + etsi(taulu, 10));
       }
   }
}
4

2 回答 2

0

Are you checking if the total sum of elements is a multiple of k? If so, you could just sum all elements and check if % (mod) k is zero (i.e. no remainder after dividing by k).

Edit: Okay I read the question again and I think the question is to find 4 numbers from the array (and duplicating the numbers are okay) to sum to k.

(Sorry I tried to delete this answer but couldn't easily)

So here's a swing at the solution: Have four nested loops, one for each "number slot". Let each loop pick one number at a time from the array (therefore allowing duplicate selections). Check the sum in the inner-most loop. If it's k, break w/ true. If not true at the end, false.

于 2013-03-18T10:50:55.157 回答
0

好的，我找到了一个不同的解决方案，它应该将时间复杂度提高到 O(n^2 log n)。这使用了一个辅助列表，该列表存储数组元素对的所有可能的总和，然后将这些总和的对的总和与 k 进行比较。这是我使用 ArrayList 的编辑方法。它工作得很好，只是它仍然太慢：作业是通过机器人测试仪提交的，而隐藏的测试显然是用大量数字进行的测试，时钟为 27.0 毫秒，而所需的最大值为 25.0 毫秒。有什么办法可以通过一些小的改动来加快代码的速度吗？

public static boolean etsi(int[] tl, int k) {
    ArrayList<Integer> summat = new ArrayList<Integer>() 
    Arrays.sort(tl);

    for (int i = 0; i < tl.length; i++) {
        for (int j = 0; j < tl.length; j++) {
            summat.add(tl[i] + tl[j]);
        }
    }
    int a = 0;
    int b = summat.size() - 1;

    for (int i = 0; i < summat.size(); i++) {
        if (summat.get(a) + summat.get(b) == k) {
            return true;
        } else if (summat.get(a) + summat.get(b) < k) {
            a++;
        } else {
            b--;
        }
    }

    return false;
 }
于 2013-03-18T11:51:36.663 回答