3Sum Cont…

Въпрос: Даден е масив nums от n цели числа, има ли елементи a, b, c в nums така че a + b + c = 0? Намерете всички уникални тройки в масива, който дава сумата нула.

Забележка:

Наборът от решения не трябва да съдържа дублиращи се триплети.

Пример:

Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Можете да видите пълния въпрос тук.

Подход 2: След ̶a̶ ̶f̶e̶w̶ много, много безполезни опити, най-накрая реших да го направя — имам предвид това!

И се натъкнах на този брилянтен пост. Подходът с две точки наистина промени играта. Ясно е, че това изисква от нас да разгледаме проблема по-подробно и да анализираме остро най-основните аспекти. Те вероятно изглеждат много основни, но могат да окажат значително влияние върху производителността.

Прости неща като -

Сортиране на масива
Уверете се, че първата и втората стойност винаги са уникални (автоматично гарантира, че третата и следователно цялата комбинация също ще бъдат уникални)

Сега нека бързо да разгледаме кода (това е точно копие на кода в публикацията в java) —

//Approach 2
//Runtime: 33ms!!!
//Memory usage: 48.6MB
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> output = new ArrayList();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; ++i) {
    // Never let i refer to the same value twice to avoid duplicates.
    if (i != 0 && nums[i] == nums[i - 1]) continue;
    int j = i + 1;
    int k = nums.length - 1;
    while (j < k) {
      if (nums[i] + nums[j] + nums[k] == 0) {
          List<Integer> list = new ArrayList();
          list.add(nums[i]);
          list.add(nums[j]);
          list.add(nums[k]);
          output.add(list);
        ++j;
        // Never let j refer to the same value twice (in an output) to avoid duplicates
        while (j < k && nums[j] == nums[j-1]) ++j;
      } else if (nums[i] + nums[j] + nums[k] < 0) {
        ++j;
      } else {
        --k;
      }
    }
  }
  return output;
    }
}

Подход 3: Малко малко ощипване — Ако сумата трябва да е 0, освен ако всички стойности не са 0, трябва да има поне едно отрицателно число. Тъй като най-външният цикъл трябва да определи първия елемент, ние ограничаваме цикъла for за отрицателни числа и числа, равни на 0. Това може да елиминира куп излишни итерации.

//Approach 3
//Runtime: 28ms
//Memory usage: 47.8MB
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> output = new ArrayList();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length && nums[i]<=0; ++i) {
    // Never let i refer to the same value twice to avoid duplicates.
    if (i != 0 && nums[i] == nums[i - 1]) continue;
    int j = i + 1;
    int k = nums.length - 1;
    while (j < k) {
      if (nums[i] + nums[j] + nums[k] == 0) {
          List<Integer> list = new ArrayList();
          list.add(nums[i]);
          list.add(nums[j]);
          list.add(nums[k]);
          output.add(list);
        ++j;
        // Never let j refer to the same value twice (in an output) to avoid duplicates
        while (j < k && nums[j] == nums[j-1]) ++j;
      } else if (nums[i] + nums[j] + nums[k] < 0) {
        ++j;
      } else {
        --k;
      }
    }
  }
  return output;
    }
}

Намерете още публикации тук.

Наздраве и Чао!

3Sum Cont…

Подобни въпроси