План курса / Все задачи / Алгоритмы и структуры данных
Сумма в сортированном массиве
легко
# решено
Дан отсортированный массив nums и число target. Нужно вернуть позиции двух чисел, которые дают в сумме target, при этом ответ гарантированно присутствует и он единственный.
Нужно вернуть сначала меньший индекс, а потом больший (индексы не могут быть равными). При этом индексация в массиве начинается с единицы, а не с нуля.
ВАЖНО: реши за O(1) по памяти
Пример 1:
Ввод: nums = [-2,1,6,9,12], target=18
Вывод: [3,5]
Объяснение: 18 = 6 + 12, 6-ка имеет индекс 3, а 12 - индекс 5
Пример 2:
Ввод: nums = [3,3,12], target=6
Вывод: [1,2]
Ограничения:
len(nums) >= 2
public class Solution
{
public static List<int> TwoSum(List<int> nums, int target)
{
int l = 0;
int r = nums.Count - 1;
while (l < r)
{
int currSum = nums[l] + nums[r];
// Если текущая сумма равна target
// -> возвращаем индексы пары чисел
if (currSum == target)
{
return new List<int> { l + 1, r + 1 };
}
// Если текущая сумма больше target
// -> сдвигаем правый указатель, чтобы уменьшить общую сумму
else if (currSum > target)
{
r--;
}
// Если текущая сумма меньше target
// -> сдвигаем левый указатель, чтобы увеличить общую сумму
else
{
l++;
}
}
return new List<int> { -1, -1 };
}
}
#include <vector>
using namespace std;
vector<int> twoSum(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
while (l < r) {
int currSum = nums[l] + nums[r];
// если текущая сумма равна target
// -> возвращаем индексы пары чисел
if (currSum == target) {
return {l + 1, r + 1};
}
// если текущая сумма больше target
// -> сдвигаем правый указатель чтобы уменьшить общую сумму
else if (currSum > target) {
r--;
}
// если текущая сумма меньше target
// -> сдвигаем левый указатель чтобы увеличить общую сумму
else {
l++;
}
}
return {-1, -1};
}
package main
func twoSum(nums []int, target int) []int {
l := 0
r := len(nums) - 1
for l < r {
currSum := nums[l] + nums[r]
// если текущая сумма равна target
// -> возвращаем индексы пары чисел
if currSum == target {
return []int{l + 1, r + 1}
}
// если текущая сумма больше target
// -> сдвигаем правый указатель чтобы уменьшить общую сумму
if currSum > target {
r--
} else {
// если текущая сумма меньше target
// -> сдвигаем левый указатель чтобы увеличить общую сумму
l++
}
}
return []int{-1, -1}
}
import java.util.*;
public class Solution {
public List<Integer> twoSum(List<Integer> nums, int target) {
int l = 0;
int r = nums.size() - 1;
while (l < r) {
int currSum = nums.get(l) + nums.get(r);
// если текущая сумма равна target
// -> возвращаем индексы пары чисел
if (currSum == target) {
return Arrays.asList(l + 1, r + 1);
}
// если текущая сумма больше target
// -> сдвигаем правый указатель чтобы уменьшить общую сумму
else if (currSum > target) {
r--;
}
// если текущая сумма меньше target
// -> сдвигаем левый указатель чтобы увеличить общую сумму
else {
l++;
}
}
return Arrays.asList(-1, -1);
}
}
from typing import *
def two_sum(nums: List[int], target: int) -> List[int]:
l = 0
r = len(nums) - 1
while l < r:
curr_sum = nums[l] + nums[r]
# если текущая сумма равна target
# -> возвращаем индексы пары чисел
if curr_sum == target:
return [l + 1, r + 1]
# если текущая сумма больше target
# -> сдвигаем правый указатель чтобы уменьшить общую сумму
elif curr_sum > target:
r -= 1
# если текущая сумма меньше target
# -> сдвигаем левый указатель чтобы увеличить общую сумму
else:
l += 1
return [-1, -1]
/**
* @param {number[]} nums
* @param {number} target
* @returns {number[]}
*/
export function twoSum(nums, target) {
let l = 0;
let r = nums.length - 1;
while (l < r) {
const currSum = nums[l] + nums[r];
// если текущая сумма равна target
// -> возвращаем индексы пары чисел
if (currSum === target) {
return [l + 1, r + 1];
}
// если текущая сумма больше target
// -> сдвигаем правый указатель чтобы уменьшить общую сумму
else if (currSum > target) {
r -= 1;
}
// если текущая сумма меньше target
// -> сдвигаем левый указатель чтобы увеличить общую сумму
else {
l += 1;
}
}
return [-1, -1];
}