ورود / ثبت نام
مساله two sum
یکی از بهترین جاهایی که شما میتونید دانش برنامه نویسیتون رو محک بزنید و حتی تقویت کنید همینجاست! جایی که با مساله های مختلف روبرو میشید، ذهنتون رو به چالش میکشید و سعی میکنید با حل مساله و کدنویسیش دانشتون رو در برنامه نویسی بالاتر ببرید. در ادامه شما با اولین مساله آشنا میکنم، یعنی مساله two sum! این مساله از سایت leetcode انتخاب کردم و کدش رو در سه زبان مختلف براتون آماده کردم.
فهرست مطالب
صورت مساله
به شما یک آرایه از اعداد صحیح (nums) و یک عدد صحیح (target) داده می‌شود. هدف این است که اندیس‌های دو عدد را در این آرایه پیدا کنید که مجموع آن‌ها برابر با عدد هدف (target) باشد. برای درک بهتر مساله 3 مثال زیر را نگاه کنید
مثال ۱:
ورودی: nums = [2,7,11,15]، هدف: 9
خروجی: [0,1]
توضیح: چون nums[0] + nums[1] = 9 است، بنابراین اندیس‌های [0, 1] را برمی‌گردانیم.
مثال ۲:
ورودی: nums = [3,2,4]، هدف: 6
خروجی: [1,2]
مثال ۳:
ورودی: nums = [3,3]، هدف: 6
خروجی: [0,1]
در این مساله فرض میکنیم که دقیقا یک جواب وجود دارد و برای درست کردن تارگت نمیتوانیم از یک عنصر بیش از یک بار استفاده کنید.
قبل از اینکه جواب این مساله رو ببنید دو تا نکته بهتون بگم. این مساله رو به چند روش میشه حل کرد. من به دو روش براتون حل میکنم. اما قبلش پیشنهاد میکنم حتما بهش فکر کنید. اگه راه حلی به ذهنتون نرسید 3 تا راهنمایی هم بهتون میکنم. در ادامه ببینید:
راهنمایی
یک روش بسیار ساده و دم دستی روش بروت فورسه (brute force) یعنی تمام جفت‌های ممکن از اعداد را بررسی کنید. این روش کنده.
برای پیدا کردن جفت اندیسها میتونید از ایده مکمل استفاده کنید. یعنی برای یک عدد ثابت مثل x کل آرایه رو بگردید و عدد y که برابر target – x رو پیدا کنید. شاید بگید که چه فرقی با قبلی داره؟ به این فکر کنید که برای جستجوی y چه کاری میشه کرد که سریعنر انجام بشه؟
این نکته در ادامه تکته قبلیه. برای اینکه جستجوی y (ایده راهنمایی 2) سریعتر بشه میتونید از hash map یا جدول هش استفاده کنید. قاعدتا باید hash map ها رو بلد باشید ولی اگه بلد نیستید آموزش یوتیوب رو ببینید.
روش 1 - بروت فورس (Brute Force)
در این روش تمام جفت‌های ممکن از عناصر را بررسی کنیم که آیا مجموع آن‌ها برابر با target (هدف) است یا خیر. برای این کار میتونیم از حلقه‌های تو در تو استفاده کنیم؛ به این صورت که حلقه بیرونی از اولین عنصر تا ماقبل آخر حرکت می‌کند و حلقه داخلی از عنصر بعدی تا آخرین عنصر رو پیمایش می‌کنه. این روش دارای پیچیدگی زمانی O(n^2) است. کد این روش رو با 3 زبان برنامه نویسی اینجا ببینید:
حل مساله با روش بروت فورس و زبان سی‌پلاس‌پلاس - ++C :
حل مساله با روش بروت فورس و زبان سی‌پلاس‌پلاس - ++C :
//C++
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {}; // No solution found
}
};
حل مساله با روش بروت فورس و زبان جاوا - Java:
//Java
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[]{}; // No solution found
}
}
حل مساله با روش بروت فورس و زبان پایتون- Python:
//Python3
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n - 1):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return [] # No solution found
اگه روش اول براتون سخته و درست درکش نکردید احتمالا مفهوم پیمایش رو خوب بلد نیستید. دو تا پیشنهاد براتون دارم: میتونید از آموزشهای سی پلاس پلاس جلسه پنجم تا هفتم رو ببینید. و یا اگر به آموزشهای ویدیویی علاقه مندید میتونید این دو تا ویدیو رو در یوتیوب ببینید:
آرایه در سی پلاس پلاس | ماتریس در سی پلاس پلاس
روش 2 - جدول هش (Hash Table)
یک روش کارآمدتر استفاده از جدول هش (unordered_map در C++) است. ما میتونیم یک بار از روی آرایه عبور کنیم و برای هر عنصر، بررسی کنیم که آیا تفاضل مقدار target منهای عنصر کنونی در جدول هش وجود دارد یا نه. اگر وجود داشته باشد، یک جفت عدد معتبر پیدا کردیم. در غیر این صورت، عنصر کنونی را به جدول هش اضافه میکنیم.
حل مساله با روش جدول هش و زبان سی‌پلاس‌پلاس - ++C :
حل مساله با روش جدول هش و زبان سی‌پلاس‌پلاس - ++C :
//C++
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> numMap;
int n = nums.size();
// Build the hash table
for (int i = 0; i < n; i++) {
numMap[nums[i]] = i;
}
// Find the complement
for (int i = 0; i < n; i++) {
int complement = target - nums[i];
if (numMap.count(complement) && numMap[complement] != i) {
return {i, numMap[complement]};
}
}
return {}; // No solution found
}
};
حل مساله با روش جدول هش و زبان جاوا - Java:
//Java
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> numMap = new HashMap<>();
int n = nums.length;
// Build the hash table
for (int i = 0; i < n; i++) {
numMap.put(nums[i], i);
}
// Find the complement
for (int i = 0; i < n; i++) {
int complement = target - nums[i];
if (numMap.containsKey(complement) && numMap.get(complement) != i) {
return new int[]{i, numMap.get(complement)};
}
}
return new int[]{}; // No solution found
}
}
حل مساله با روش جدول هش و زبان پایتون- Python:
//Python3
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
numMap = {}
n = len(nums)
# Build the hash table
for i in range(n):
numMap[nums[i]] = i
# Find the complement
for i in range(n):
complement = target - nums[i]
if complement in numMap and numMap[complement] != i:
return [i, numMap[complement]]
return [] # No solution found
سخن پایانی
من در این نوشته این مساله رو در قالب دو روش براتون حل کردم. ممکنه هر دو روش رو به خوبی یاد گرفته باشید که چه عالی! و یا اینکه در یادگیری روش دوم کمی به مشکل بخورید. در روش دوم از مفهوم hash استفاده کردم که من در آموزشهای ساختمان داده قراره این مفاهیم رو آموزش بدم.
اگه دوست دارید در برنامه نویسی پیشرفت کنید باید بدونید که در کنار یادگیری سینتکس و دستورات برنامه نویسی باید هنر حل مساله رو یاد بگیرید. حل مساله به این معنی که وقتی یک مساله به شما میدن شما بتونید به این مساله فکر کنید، براش راه حل پیدا کنید و در نهایت کدنویسیش کنید. شما حل مساله های زیاد میتونید به این توانایی برسید