Блог

Представьте, что вам дан несортированный массив [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] и проверьте их позже по их парам), затем верните пару с обоими наибольшими значениями, но запутались.

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

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

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

Алгоритм:

1. Отсортируйте массив.
2. Имейте два указателя startIndex и endIndex на 0 и arraySize-1.
3. сумма = arr[startIndex] arr[endIndex]
4. Если сумма меньше или равна 23, увеличьте начальный индекс, иначе уменьшите конечный индекс.
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(nlogn)

O(n), если массив уже был отсортирован

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