Как использовать C, чтобы правильно решить две суммы?


Проблема Двух Сумм:

Дан массив целых чисел, индексы доходности двух чисел таких, что они складываются в определенную цель.

Можно предположить, что каждый вход будет иметь ровно одно решение, и вы можете не использовать дважды один и тот же элемент.

Пример:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Код:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target){
    int *a = malloc(sizeof(int) * 2);
    for(int i = 0; i < numsSize; i++){
        for(int j = i+1; j < numsSize; j++){
            if (nums[i] + nums[j] == target){
                a[0] = i;
                a[1] = j;
                return a;
            }
        }
    }
} /* Error: control reaches end of non-void function [-Werror=return-type] */


138
-1
задан 13 апреля 2018 в 07:04 Источник Поделиться
Комментарии
1 ответ

Я бы сделал так:

/**
* Note: The returned array must be malloced, assume caller calls free().
*/
#define INVALID (-1)
int* twoSum(int* nums, int numsSize, int target)
{
int *result = malloc(sizeof(int) * 2);
memset (result, INVALID, sizeof(int) * 2);
for(int left = 0; left < numsSize && result[0] == INVALID; left++)
{
for(int right = left+ 1; right < numsSize && result[0] == INVALID; right++)
{
if (nums[left] + nums[right] == target)
{
result[0] = left;
result[1] = right;
/* A return statement here instead of the overhead of the
second check in the for loop conditions may be a good
idea, it depends if the driving factor is performance
or maintainability */
}
}
}
return result;
}

Так как это интервью вопрос, А вы показываете, что сияющая звезда вы, возможно, захотите рассмотреть следующие моменты:


  • Все возможное, чтобы избежать многократного возврата очков, если вы можете, но есть
    будет удар по производительности. Добавляя комментарий, Я думаю, что у меня
    показал, что я определил этим вопросом и, правильно или неправильно сделал
    решение и объяснил, почему.

  • Установлении результатов как можно скорее может быть пустой тратой несколько
    циклов процессора, но это поможет, если код пойдет не так, вы знаете
    вы будете иметь случайные значения тайком, представьте себе, что
    произойдет, если results[0] = 5;

  • Используя однобуквенные переменные означает, что вы не имеете право больше
    комментарии/документы, чтобы объяснить свой код. Это интервью
    вопрос, вы не хотите представить документ 20 страниц подробно, что
    а, я, J означает, и их диапазон значений вы. (левый и правый
    не очень описательные имена, но они лучше, чем I и J).

Все, что я делал, было добавить одну строку и отполировать какашку немного, что намного легче, когда я не даю интервью, удачи !

0
ответ дан 13 апреля 2018 в 12:04 Источник Поделиться