170. Two Sum III - Data structure design

LeetCode easy оригинал: C# #array #backtracking #csharp #design #easy #leetcode #search #sort #two-pointers

LeetCode Static

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

Реализуйте класс TwoSum:

- TwoSum() инициализирует объект TwoSum с изначально пустым массивом.

- void add(int number) добавляет число в структуру данных.

- boolean find(int value) возвращает true, если существует хотя бы одна пара чисел, сумма которых равна значению value, в противном случае возвращает false.

Пример:

Input

["TwoSum", "add", "add", "add", "find", "find"]

[[], [1], [3], [5], [4], [7]]

Output

[null, null, null, null, true, false]

C# решение

сопоставлено/оригинал

public class TwoSum {
    private List<int> nums;
    private bool is_sorted;
    public TwoSum() {
        this.nums = new List<int>();
        this.is_sorted = false;
    }
    public void Add(int number) {
        this.nums.Add(number);
        this.is_sorted = false;
    }
    public bool Find(int value) {
        if (!this.is_sorted) {
            this.nums.Sort();
            this.is_sorted = true;
        }
        int low = 0, high = this.nums.Count - 1;
        while (low < high) {
            int twosum = this.nums[low] + this.nums[high];
            if (twosum < value)
                low += 1;
            else if (twosum > value)
                high -= 1;
            else
                return true;
        }
        return false;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TwoSum {
    private List<int> nums;
    private bool is_sorted;
    public TwoSum() {
        this.nums = new List<int>();
        this.is_sorted = false;
    }
    public void Add(int number) {
        this.nums.push_back(number);
        this.is_sorted = false;
    }
    public bool Find(int value) {
        if (!this.is_sorted) {
            this.nums.Sort();
            this.is_sorted = true;
        }
        int low = 0, high = this.nums.size() - 1;
        while (low < high) {
            int twosum = this.nums[low] + this.nums[high];
            if (twosum < value)
                low += 1;
            else if (twosum > value)
                high -= 1;
            else
                return true;
        }
        return false;
    }
}

Java решение

сопоставлено/оригинал

import java.util.Collections;

class TwoSum {
    private ArrayList<Integer> nums;
    private boolean is_sorted;
    public TwoSum() {
        this.nums = new ArrayList<Integer>();
        this.is_sorted = false;
    }
    public void add(int number) {
        this.nums.add(number);
        this.is_sorted = false;
    }
    public boolean find(int value) {
        if (!this.is_sorted) {
            Collections.sort(this.nums);
            this.is_sorted = true;
        }
        int low = 0, high = this.nums.size() - 1;
        while (low < high) {
            int twosum = this.nums.get(low) + this.nums.get(high);
            if (twosum < value) low += 1;
            else if (twosum > value) high -= 1;
            else return true;
        }
        return false;
    }
}

JavaScript решение

сопоставлено/оригинал

class TwoSum {
    constructor() {
        this.nums = [];
        this.is_sorted = false;
    }

    add(number) {
        this.nums.push(number);
        this.is_sorted = false;
    }

    find(value) {
        if (!this.is_sorted) {
            this.nums.sort((a, b) => a - b);
            this.is_sorted = true;
        }

        let low = 0,
            high = this.nums.length - 1;
        while (low < high) {
            let twosum = this.nums[low] + this.nums[high];
            if (twosum < value) low += 1;
            else if (twosum > value) high -= 1;
            else return true;
        }
        return false;
    }
}

Python решение

сопоставлено/оригинал

class TwoSum(object):

    def __init__(self) -> None:
       
        self.nums = []
        self.is_sorted = False

    def add(self, number: int) -> None:
        self.nums.append(number)
        self.is_sorted = False

    def find(self, value: int) -> bool:
        if not self.is_sorted:
            self.nums.sort()
            self.is_sorted = True

        low, high = 0, len(self.nums) - 1
        while low < high:
            currSum = self.nums[low] + self.nums[high]
            if currSum < value:
                low += 1
            elif currSum > value:
                high -= 1
            else: return True

        return False

Go решение

сопоставлено/оригинал

type TwoSum struct {
    nums      []int
    is_sorted bool
}

func Constructor() TwoSum {
    return TwoSum{nums: []int{}, is_sorted: false}
}

func (this *TwoSum) Add(number int) {
    this.nums = append(this.nums, number)
    this.is_sorted = false
}

func (this *TwoSum) Find(value int) bool {
    if !this.is_sorted {
        sort.Ints(this.nums)
        this.is_sorted = true
    }
    low, high := 0, len(this.nums)-1
    for low < high {
        var twosum int = this.nums[low] + this.nums[high]
        if twosum < value {
            low += 1
        } else if twosum > value {
            high -= 1
        } else {
            return true
        }
    }
    return false
}

Algorithm

1️⃣

Инициализация указателей:

Инициализируйте два указателя low и high, которые указывают на первый и последний элементы списка соответственно.

2️⃣

Итерация с использованием двух указателей:

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.