在整数数组中查找自定义元素数的总和

Question

我正在面试一位大型技术人员，在解决问题的回合中，我被问到一个编程问题。除了一个棘手的约束外，这个问题与 Leet Code 中的 Two Sum 问题非常相似。问题是这样的：给定一个整数数组 nums、一个整数目标和一个整数限制，return 正好有一组元素可以达到给定的限制并加起来达到给定的目标。

 Input: nums = [2,7,11,15], target = 20, limit = 3
 
 Output: [2, 7, 11]

解释：目标是 20，限制是 3，所以，我们必须从数组中找到 3 个数字相加等于 20。

我在面试中未能解决这个问题，此后一直在寻找解决方案。蛮力方法是运行与限制一样多的循环，这是不可行的，考虑到限制可能 <= 10,000

另一种是提取长度为 limit 的子数组，运行通过每个子数组，添加它们的元素和 return 一个子数组，总和为 Target。

但是，我相信一定有更有效的方法来解决这个问题。有什么想法吗？

编辑：

我们return的输出可能是随机的，不一定是连续的。

必须满足限制，我们 return 的元素数量必须等于限制。

数组大小没有限制

Answer 1

使用堆栈（递归地）查找数组元素，这些元素将在所需的数组元素限制内求和为所需的目标。这样做实际上会找到所有组合，但只有那些使用落在元素限制上的组合才会被放入列表中。

请阅读代码中的注释。如果你愿意，稍后删除它们。这是一个演示此过程的可运行程序：

package sumtargetlimit_demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;


public class SumTargetLimit_Demo {

    // The desired Target Sum
    private int targetSum = 20;
    
    /* The max allowable array elements to use in order to acquire 
       the desired Target Sum.    */
    private int numbersLimit = 3;
    
    // A Stack to hold the Array elements which sum to the desired Target Sum.
    private Stack<Integer> stack = new Stack<>();

    // Store the summation of current elements held in stack.
    private int sumInStack = 0;
    
    /* A List Interface of Integer[] array to hold all the 
       combinations of array elements which sum to target. */
    private List<Integer[]> combinationsList = new ArrayList<>();
    
    
    public static void main(String[] args) {
        // Demo started this way to avoid the need for statics.
        new SumTargetLimit_Demo().startDemo(args);
    }
    
    private void startDemo(String[] args) {
        // The int array to work against.
        int[] intData = {2, 7, 11, 15};
        
        /* See which array elements can acquire the desired 
           Target Sum with the maximum number of array elements 
           specified in the numbersLimit member variable.     */
        getSummations(intData, 0, intData.length);
        
        // Display the found results to Console window...
        if (combinationsList.isEmpty()) {
            System.err.println("No integer elements within the supplied Array will");
            System.err.println("provide a Taget Sum of " + targetSum + " with a maximum number");
            System.err.println("limit of " + numbersLimit + ".");
        }
        else {
            for (Integer[] intArray : combinationsList) {
                System.out.println(Arrays.toString(intArray).replaceAll("[\[\]]", ""));
            }
        }
    }
    
    // Note: This method is recursive...
    public void getSummations(int[] data, int startIndex, int endIndex) {
        /* Check to see if the sum of array elements stored in the
           Stack is equal to the desired Target Sum. If it is then 
           convert the array elements in the Stack to an Integer[] 
           Array and add it to the conmbinationsList List.       */
        if (sumInStack == targetSum) {
            if (stack.size() <= numbersLimit) {
                combinationsList.add(stack.toArray(new Integer[stack.size()]));
            }
        }

        for (int currIndex = startIndex; currIndex < endIndex; currIndex++) {
            if (sumInStack + data[currIndex] <= targetSum) {
                stack.push(data[currIndex]);
                sumInStack += data[currIndex];

                // Make the currentIndex +1, and then use recursion to carry on.
                getSummations(data, currIndex + 1, endIndex);
                sumInStack -= stack.pop();
            }
        }
    }
    
}

尝试更大的 int[] 数组并尝试使用目标总和和数字限制，看看效果如何。

Answer 2

换个角度看这个问题，就是用动态规划的眼光。对于数组中的任意一个元素，有两种情况：

它会是组成和的元素的一部分，在这种情况下，我们递归地找到组成剩余和的元素，限制为-1。
不会是组成和的元素的一部分，在这种情况下，我们在数组的剩余部分中寻找目标。

这里是遵循上述逻辑的示例：

import java.util.*;
class HelloWorld {
    static Map<Integer, List<Integer>> cache = new HashMap<>();
    public static void main(String[] args) {
        int[] array = {9, 2, 15, 11, 7, 23, 54, 50, 12};
        int limit = 4;
        int target = 35;
        // This is to optimize the search for element in case the limit is 1
        Arrays.sort(array);
        List<Integer> subarray = getElementsWithSumEqualToTarget(array, 0, limit, target);
        System.out.println(subarray);
    }
    static List<Integer> getElementsWithSumEqualToTarget(int[] array, int startingIndex, int limit, int target) {
         // If limit is 0, or we have reached the end of the array then sum doesn't exists.
        if(limit == 0 || startingIndex >= array.length) {
            return null;
        } else if(limit == 1) {
            // For limit 1, we can do a simple binary search, or linear search in that case Arrays.sort can be removed
            int index = Arrays.binarySearch(array, startingIndex, array.length - 1, target);
            if(index < 0) {
                return null;
            }
            ArrayList<Integer> list = new ArrayList();
            list.add(target);
            return list;
        } else if (cache.containsKey(target)) {
          // If for a given sum, the subarray of elements, is already present, we can return it from the cache.(Memoization) 
            return cache.get(target);
        }
        // Case 1: The current element will be part of the sum.
        List<Integer> subarray = getElementsWithSumEqualToTarget(array, startingIndex + 1, limit - 1, target - array[startingIndex]);
        if(subarray != null) {
            subarray.add(array[startingIndex]);
            // Add target and subarray to the cache
            cache.put(target, subarray);
            return subarray;
        }
        // Case 2: Current element is not part of the sum
        subarray = getElementsWithSumEqualToTarget(array, startingIndex + 1, limit, target);
        if(subarray != null) {
            cache.put(target, subarray);
        }
        return subarray;
    }
}

请在大型数据集上尝试一下，看看效果如何。希望对您有所帮助。

在整数数组中查找自定义元素数的总和

Find the sum of custom number of elements in an array of Integers

java

arrays