Всем привет, меня зовут Тан Лян.
В настоящее время серия C++ обновляется каждый день, а решения LeetCode обновляются нерегулярно.По оценкам Лао Ляна, скорость составляет от одной до двух статей в неделю. Если вам нравится такая статья, пожалуйста, поддержите ее.github
Что ж, без лишних слов, давайте рассмотрим тему.
смысл названия
Дан массив всех целых чиселnumsи целое числоtarget, требуется вернуть два индекса, чтобы сумма, соответствующая двум индексам в массиве, была равна target.
Вы можете предположить, что для определенного значения есть ответ, и что элемент нельзя использовать дважды.
в:
2 <= nums.length <= 1e4-1e9 <= nums[i] <= 1e9-1e9 <= target <= 1e9
Решение 1. Безмозглое перечисление
Найдите в данных два числа, равныеtarget, понятно, что перечисление возможно.
Однако для использования перечисления необходимо решить несколько проблем.Во-первых, требуется количество перечислений. В этой задаче нам нужно перечислить комбинацию любых двух чисел.Для массива длины n мы знаем, что такая комбинация имеет в суммевидов, порядков ивполне, поэтому приближение можно рассматривать каксвоего рода.
Для этой задачи максимальная длина массива равна1e4, величина после возведения в квадрат равна1e8, что почти на порядок больше, чем C++ может выполнить за одну секунду. Едва ли приемлема высокая вероятность того, что он не истечет по таймауту.
Во-вторых, есть случай повторения. Ведь комбинаций двоек и двоек так много, как сделать так, чтобы результат ответа был уникальным? А если не один?
К счастью, этот вопрос нас гарантировал, смысл вопроса ясно изложен, а ответ уникален. В этом случае мы можем смело писать код:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
vector<int> ret;
for (int i = 0; i < n; i ++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) {
ret.push_back(i);
ret.push_back(j);
return ret;
}
}
}
return ret;
}
};
Решение 2. Используйте карту
После отправки кода решения 1 время прохождения составляет около 400 миллисекунд, что превышает только 6% пользователей Очевидно, что это не идеально, и есть много возможностей для оптимизации.
Итак, как мы его оптимизируем?
Очевидно, более интуитивно понятно, что мы перечисляем все возможности, что отнимает слишком много времени.Есть ли способ не перебирать все комбинации, но все же гарантировать, что мы сможем найти ответ?
Ответ конечно да, и принцип использования тоже очень прост, мы знаемtarget, вам нужно найти два числа a и b в массиве, так чтоa+b=target. Но на самом деле нам не нужно проходить все комбинации A и B, потому что a и b определяются, и она равнаtarget-a. Так что нам просто нужно перечислить все, а затем судитьtarget-aСуществует элемент или нет.
Так что вопрос в том, как мы судимtarget-aСуществует ли он и находит ли он свое местонахождение?
Ответ прост, используйте карту в STL. map может записывать пару , в качестве ключа мы берем число в массиве, а в качестве значения — позицию, в которой оно появляется. Таким образом, нам нужно только заранее вставить все элементы массива в карту, и все.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
vector<int> ret;
map<int, int> mp;
// 先把数组中元素插入map
for (int i = 0; i < n; i++) {
mp[nums[i]] = i;
}
for (int i = 0; i < n; i++) {
// 枚举a，通过map判断target - a是否存在
int num2 = target - nums[i];
if (mp.count(num2)) {
ret.push_back(i);
ret.push_back(mp[num2]);
}
}
return ret;
}
};
Этот код также очень прост, но не спешите радоваться, если вы отправите его, вы обнаружите, что приведенный выше код не пройдет. Почему не может пройти? Поскольку мы упустили из виду ситуацию, мы обычно называем эту скрытую и трудную для размышления ситуацию «Уловкой», которую можно рассматривать как уловку, используемую вопрошающим.
Иногда, даже если я думаю о том, чтобы понять метод, но не нахожу скрытого подвоха, я не могу пройти мимо вопроса. Так что мы должны не только придумать алгоритмы, но и убедиться, что алгоритмы работают во всех крайних случаях.
В этом вопросе хитрость заключается в уникальности элемента. Поскольку мы используем карту, карта требует, чтобы все ключи были уникальными. Если в массиве есть повторяющиеся элементы, данные, считанные позже, перезапишут предыдущие. В чем проблема перезаписать? Очевидно, приводит к неправильному ответу.
Итак, вот вопрос, в этом вопросеnumsНомер уникален? В заголовке об этом не говорится, в заголовке говорится только о том, что существует только одно решение, но не говорится, что каждый элемент уникален. Поэтому, хотя в заголовке ясно не сказано, нам все же необходимо проанализировать этот вопрос.
Предположим, мы находимa+b=targetответьте, здесь могут быть дубликаты a и b? Очевидно, что если a и b не равны, ни одно из них не будет повторяться. Потому что если в массиве два a, значит, мы можем найти как минимум две комбинации a и b. Это имеет только одно противоречие с решением, упомянутым в заголовке, поэтому очевидно, что когда a и b не равны, они появятся только один раз.
Тогда остальное, когда a и b равны, что является хитростью этого вопроса. a и b могут быть равны, но поскольку ключ должен быть уникальным в карте, можно найти только один. Как это решить? На самом деле, это очень просто, нам нужно только добавить условие суждения, чтобы решить его:
添加备注
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
vector<int> ret;
map<int, int> mp;
for (int i = 0; i < n; i++) {
mp[nums[i]] = i;
}
for (int i = 0; i < n; i++) {
int num2 = target - nums[i];
// 额外增加了mp[num2] != i的条件
if (mp.count(num2) && mp[num2] != i) {
ret.push_back(i);
ret.push_back(mp[num2]);
break;
}
}
return ret;
}
};
Этот код почти такой же, как и выше, за исключением того, что условие mp[num2] != i добавлено к решению if цикла for ниже. Это условие гарантирует, что мы найдемnum2не текущийnums[i], так как при равенстве a и b мы хотим найти позицию b через карту, в результате из-за перезаписи в карте восстанавливается позиция a, что вызывает ошибку. Мы можем избежать этого, добавив это суждение.
На этом еще не все, этот код еще можно оптимизировать. Поскольку карта будет перезаписана, нам фактически не нужно вставлять все элементы в начале, мы можем делать выводы во время вставки элементов.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
vector<int> ret;
map<int, int> mp;
for (int i = 0; i < n; i++) {
int num2 = target - nums[i];
// 先寻找num2是否存在
if (mp.count(num2)) {
ret.push_back(mp[num2]);
ret.push_back(i);
return ret;
}
mp[nums[i]] = i;
}
return ret;
}
};
В этом коде мы не началиnumsВсе элементы массива помещаются в карту. Вместо этого он постепенно вставляется с помощью цикла for.В цикле for мы сначала находимnum2Существует ли он на карте, а затем вставьте егоnums[i]. Мы не ходили судитьmp[nums2] != i, потому что на этот разnums[i]Значения не были вставлены в карту, поэтому они не должны совпадать.
На самом деле, это использует коммутативный закон сложения,a+b=targetтакже доступныb+a=target. Два числа a и b должны иметь последовательность в массиве, предполагая, что a находится перед b. Поскольку мы не вставили все элементы в карту заранее, мы не можем найти b в данный момент, то есть не можем найти ответ. Но когда мы идем к b, мы должны найти a. А так как мы сначала судим, а потом вставляем текущий элемент, даже если a и b равны, перезаписи не произойдет.
На данный момент, даже если мы действительно закончили эту задачу, мы не только сделали это, но и максимально оптимизировали. Очевидно, что это очень простая тема, и в ней не используются какие-либо продвинутые алгоритмы, но когда мы изучаем ее подробно, можно сказать так много вещей. В какой-то степени это тоже одна из прелестей алгоритмов. Мелкие детали заслуживают тщательного изучения и анализа, а результаты можно анализировать. Даже решение многих задач основано на этих маленьких анализах.
Ну вот и все по этой теме, спасибо за прочтение.