java - 如何使用递归算法确定数组是否包含两个总和为给定整数的元素？

Question

好的，谢谢大家的帮助!特别感谢@pjs 让我知道如何去做。这是我的新代码，但由于某种原因，它不会达到基本情况之一。抱歉，如果我删除了旧代码，这是我第一次在这里发帖，我不确定是否应该用新代码回答我自己的问题。

//initialized int start = 0
//initialized int end = length of the array
//here goes the constructor

public boolean kPairSum(Integer k) {
        if (sortedIntegerArray.length < 2) {      //if array is less than two return false
            return false;
        }
        else if (start == end) {                  //once the start and the end meets. This is the base case that doesn't seem to work for me.
            return false;
        }
        else {
            int currentStart = sortedIntegerArray[start];   //get first int in the array
            int currentEnd = sortedIntegerArray[end-1];     //get the very last int in the array
            int sum = currentStart + currentEnd;            //get the sum 

            if (k.equals(sum)) {                            //compare sum and k if equal
                return true;
            }
            else if (sum <k) {                              //if sum is less than k then increment value of start
                start++; 
                return kPairSum(k);
            }
            else if (sum > k) {                             //if sum is greater than k then it decrements value of end
                end--;
                return kPairSum(k);
            }
            else {                                          //not sure if this is right, should I just get rid of the else if statement for sum > k and change it to just an else? I wrote this down cause it has to return a type of boolean.
                return kPairSum(k);
            }

        }

Answer 1

您的数组名为 sortedIntegerArray，但您似乎没有利用这一事实。

首先对数组的两端求和。如果总和小于 k，则总和的两个元素之一必须更大。由于元素是有序的，因此您只能通过递增较低的索引来获得更大的值。类似地，如果总和大于k，则两个元素之一必须更小，因此您需要递减上索引。在任何一种情况下，问题的结构都是相同的，但您现在正在对数组的一个子集进行操作，该数组由您递增/递减的索引指定。基本情况是您找到两个总和为 k 的值，或者索引在某处相遇。递归应该跳到你身上。由于每个递归调用都会递增或递减边界索引，直到它们在中间相遇，所以它是 O(n)。