Как найти два оптимальных веса в векторе?

Question

Представьте, что вы получили несортированный массив [5,11,7,4,19,8,11,6,17] и максимальный вес 23. [похоже на проблему двух сумм немного по-другому]

Нужно найти два оптимальных веса (под этим я подразумеваю, если два веса, которые (почти или нет) составляют половину веса, который вы пытаетесь найти) в этом случае [5,17], [3,19], [11,11], поэтому мне нужно вернуть [11,11].

Я забрал проблему и не смог ее решить.[Мне не разрешали использовать структуры]

Я пытался сортировать [3, 5, 6, 7, 8, 11, 11, 17, 19] и искать с обоих концов и хранить индексы значений, которые были<= максимальный вес в векторе в виде пары (например, v [i], v [i + 1] и проверяем их позже по их парам), затем возвращаем пару с обоими наибольшими значениями, но запутались. </p>

[хотя веса были двойными, и я не видел дубликатов в этом наборе, я не использовал unsorted_map (hashMap), возможно, это сработало?]

Кто-нибудь может подсказать, как мне решить эту проблему?это похоже на "проблему ранца"?Спасибо

Answer 1

Вы можете использовать Двухточечный подход для решения проблемы.

Алгоритм:

1. Сортировать массив.
2. Имеют два указателя startIndex и endIndex на 0 и arraySize-1..
3. sum = arr [startIndex] + arr [endIndex]
4. Если сумма меньше или равна23, приращение startIndex, иначе уменьшение endIndex.
5. отслеживание ближайшего значения с использованием переменной.
6. окончание при запуске startIndex == endIndex

код в Java:

    public class Solution {


    private ArrayList<Integer> twoSumClosest(ArrayList<Integer> a, int s) {

      // Sort the arraylist
      Collections.sort(a);

      // closests sum we got till now
      int sumClosest = Integer.MIN_VALUE;

      // indexes used to traverse
      int startIndex = 0;
      int endIndex = a.size() - 1 ;

      // answer Indexes
      int firstIndex = 1;
      int secondIndex = a.size() - 1;

      while( startIndex < endIndex ) {
        if( a.get(startIndex)  + a.get(endIndex)  > s) {
          endIndex--;
          continue;
        } else {
          if( a.get(startIndex)  + a.get(endIndex)  > sumClosest ) {
            sumClosest = a.get(startIndex)  + a.get(endIndex);
            firstIndex = startIndex;
            secondIndex = endIndex;
          }
          startIndex++;
        }
      }

      ArrayList<Integer> ans = new ArrayList<>();
      ans.add(firstIndex);
      ans.add(secondIndex);
      return ans;
    }

  }

Сложность времени: O (n)

Требуется дополнительное пространство: O (1)