java - 两个总和 : How is the solution with O(1) space complexity implemented?

Question

LeetCode 中描述了经典的二和问题。 .

我知道如何使用哈希表来解决它，这会导致 O(n) 额外空间。现在我想用O(1)空间解决，所以我先对数组进行排序，然后用两个指针找到这两个整数，如下面(不正确的)代码所示。

public int[] twoSum(int[] numbers, int target) {
        java.util.Arrays.sort(numbers);
        int start = 0, end = numbers.length - 1;
        while(start < end) {
            if(numbers[start] + numbers[end] < target) {
                start++;
            }
            else if(numbers[start] + numbers[end] > target) {
                end--;
            }
            else {
                int[] result = {start + 1, end + 1};
                return result;
            }
        }
        return null;
}

此代码不正确:我在排序后返回索引。那么我将如何跟踪所选整数的原始索引？还是有其他 O(1) 空间解决方案？谢谢。

Answer 1

如果你只关心空间复杂度，而不是时间复杂度，那么你就不需要排序。这样一来，跟踪原始索引的整个问题就迎刃而解了。

int[] twoSum(int[] numbers, int target) {
    for (int i = 0; i < numbers.length-1; i++) {
        for (int j = i+1; j < numbers.length; j++) {
            if (numbers[i] + numbers[j] == target)
                return new int[]{i+1, j+1};
        }
    }
    return null;
}

如果您想返回所有这样的对，而不仅仅是第一个，那么只需继续迭代而不是立即返回(当然，返回类型必须更改为列表或二维数组或.. .).