Блог

У меня возникли трудности с этим вопросом. Итак, я пытаюсь отобразить правильные решения в виде строк, но испытываю трудности с последним циклом for. Также есть ли способ отсортировать эти массивы или просто добавить функцию Arrays.sort?

Вопросы следуют:

 //Given an array nums of n integers, are there elements a, b, c in nums such that a   b   c = 0? Find all //unique triplets in the array which gives the sum of zero.

//Note:

//The solution set must not contain duplicate triplets.

//Example:

//Given array nums = [-1, 0, 1, 2, -1, -4],

//A solution set is:
//[
//  [-1, 0, 1],
//  [-1, -1, 2]
//]
  

и это то, что у меня есть до сих пор

 
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //Arrays.sort(nums);
        int isZero = 0;
        
        for(int i = 0; i < nums.length; i  )
        {
            for(int j = i 1; j< nums.length; j  )
            {
                for(int x = i   2; x < nums.length;x   )
                {
                    if(nums[i]   nums[j]  nums[x] == isZero)
                    {
                        
                       
                    }
                }
            }
        }
        return Collections.emptyList();
        
    }
}

  

Вам нужен внешний List для хранения массивов, и при каждом совпадении сохраняйте 3 значения

 public List<List<Integer>> threeSum(int[] nums) {
    int isZero = 0;
    List<List<Integer>> result = new ArrayList<>();

    for(int i = 0; i < nums.length; i  ){
        for(int j = i 1; j< nums.length; j  ){
            for(int x = i   2; x < nums.length;x   ){
                if(nums[i]   nums[j]  nums[x] == isZero){
                    result.add(Arrays.asList(nums[i], nums[j], nums[x]));
                }
            }
        }
    }
    return resu<        
}
  

Если вы имели в виду, что так сортируют триплеты, и поэтому у них нет дубликатов,

• используйте Set
• отсортируйте внутренний список перед
• вы можете удалить бесполезную итерацию с помощью -2 и -1 на конечной границе 2 первых циклов

 public static Set<List<Integer>> threeSum(int[] nums) {
    Set<List<Integer>> result = new HashSet<>();
    int isZero = 0;
    for (int i = 0; i < nums.length - 2; i  ) {
        for (int j = i   1; j < nums.length - 1; j  ) {
            for (int x = i   2; x < nums.length; x  ) {
                if (nums[i]   nums[j]   nums[x] == isZero) {
                    List<Integer> tmp = Arrays.asList(nums[i], nums[j], nums[x]);
                    tmp.sort(Comparator.naturalOrder());
                    result.add(tmp);
                }
            }
        }
    }
    return resu<
}
  

Приведенный ниже код проходит все тесты. Единственной проблемой является временная сложность O (n * 2), где время превышает очень БОЛЬШИЕ входные данные. Добро пожаловать, если кто-то улучшит алгоритм.

 class Solution {
public List<List<Integer>> threeSum(int[] A) {
    
 if ( A.length <= 2 ) return List.of();
    
    Set<List<Integer>> set = new HashSet<>();
    
    for (int i = 0; i < A.length;   i) {
        
        for (int j = i   1; j < A.length ;   j) {
            int thirdNumber = - ( A[i]   A[j] ) ;
            List<Integer> tempp = Arrays.stream(A).boxed().collect(Collectors.toList());
            tempp.remove(Integer.valueOf(A[i]));
            tempp.remove(Integer.valueOf(A[j]));
            if (tempp.contains(Integer.valueOf(thirdNumber))) {
                List<Integer> temp = Arrays.asList(A[i], A[j], thirdNumber);
                Collections.sort(temp);
                set.add(temp);
            }               
        }
    }
    
    return new ArrayList<>(set);
}
  

}

Вы можете отсортировать массив перед сбором этих триплетов, тогда эти триплеты также будут отсортированы.

   public Set<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);  // Sort the array
    for (int i = 0; i < nums.length; i  ) {
      for (int j = i   1; j < nums.length; j  ) {
        for (int x = j   1; x < nums.length; x  ) {
          if (nums[i]   nums[j]   nums[x] == 0) {
            res.add(Arrays.asList(nums[i], nums[j], nums[x]));
          }
        }
      }
    }
    return res;
  }