c - 如何在不循环的情况下扫描并比较数组中的值

Question

我有一项任务需要扫描多个案例。在每种情况下，都会给您一个数组和一个目标。目标是扫描数组以找到一组加起来达到目标​​的两个数字。

我的问题是我需要让我的 big-oh(运行时间)等于 n，这意味着我最多可以有一个循环。这是我现在的代码。

//Assume that cases, sizeofarray, array, and target already exist.    
while(cases =! 0){
        scanf("%d", @sizeofarray);
        scanf("%d", @target);

        array = malloc(sizeof(int) * sizeofarray);
    }

正如您所看到的，针对多种情况运行的要求已经消除了我在函数中使用其他循环的能力。因此，我需要扫描并比较数组中的值，而不使用 for 循环。

我想另一个选择是不使用 case 值循环，从而使我能够在其他地方使用循环并使我的 big-oh 运行时间低于 n。

如果有人能帮助我，我将不胜感激。重申一下，我需要知道是否存在一种技术可以在不循环的情况下将值扫描到数组中，在不循环的情况下比较数组中的值，或者在不循环的情况下扫描多个案例。

Answer 1

这是一个经典的二和问题。使用HashMap来存储目标值。我提供了一个Java示例供您引用。我认为它可以很容易地转换为C++代码

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    int[] result = new int[2];

    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(numbers[i])) {
            int index = map.get(numbers[i]);
            result[0] = index+1 ;
            result[1] = i+1;
            break;
        } else {
            map.put(target - numbers[i], i);
        }
    }

    return result;
    }
}

时间复杂度取决于 HashMap 的 put 和 get 操作，通常为 O(1)。

该解决方案的时间复杂度为 O(n)。