در این مطلب، ویدئو TWO SUM II – سوال مصاحبه کدنویسی آمازون – Leetcode 167 – Python با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:08:18
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,000 –> 00:00:03,720
کد نشتی 167 به برخی از آنها چیست، بنابراین
2
00:00:03,720 –> 00:00:05,250
یک آرایه ورودی به ما داده می شود که
3
00:00:05,250 –> 00:00:08,189
قبلاً به ترتیب صعودی مرتب شده است و می
4
00:00:08,189 –> 00:00:10,920
خواهیم دو عدد را پیدا کنیم که جمع
5
00:00:10,920 –> 00:00:13,200
آنها هدفی است که به ما نیز داده شده است، بنابراین در
6
00:00:13,200 –> 00:00:15,389
این مورد هدف 9 است. دو
7
00:00:15,389 –> 00:00:17,010
عددی که در این آرایه تا 9 جمع می
8
00:00:17,010 –> 00:00:20,100
شوند، دو و هفت هستند و ما می
9
00:00:20,100 –> 00:00:22,410
خواهیم شاخص های این دو مقدار را برگردانیم،
10
00:00:22,410 –> 00:00:25,109
اما نکته اینجاست که شاخص
11
00:00:25,109 –> 00:00:28,109
ها بر اساس یک هستند و بر اساس صفر نیستند، بنابراین
12
00:00:28,109 –> 00:00:30,570
عنصر اول دارای شاخص 1 است.
13
00:00:30,570 –> 00:00:31,740
عنصر دوم دارای شاخص 2 است
14
00:00:31,740 –> 00:00:33,239
، نمیدانم چرا دقیقاً
15
00:00:33,239 –> 00:00:34,860
در این مشکل این کار را انجام دادند، این یک جور عجیب است،
16
00:00:34,860 –> 00:00:36,450
اما به دلایلی این کار را انجام دادند، همچنین
17
00:00:36,450 –> 00:00:38,219
تضمین میکنیم که دقیقاً یک
18
00:00:38,219 –> 00:00:40,410
راهحل وجود دارد و نمیتوانیم از همان
19
00:00:40,410 –> 00:00:42,989
عدد دو بار استفاده کنیم، بنابراین در این مثال که
20
00:00:42,989 –> 00:00:45,149
آنها دو عدد را به ما دادند که دو
21
00:00:45,149 –> 00:00:46,980
عدد اول به هدف خلاصه می شود،
22
00:00:46,980 –> 00:00:48,930
بنابراین واقعاً مثال خوبی نیست، بنابراین من می
23
00:00:48,930 –> 00:00:50,640
خواهم به مثال خود در اینجا که کشیده
24
00:00:50,640 –> 00:00:53,250
ام نگاه کنم، بنابراین اولین ایده ای که ممکن است
25
00:00:53,250 –> 00:00:55,260
به ذهن شما برسد این است فقط به
26
00:00:55,260 –> 00:00:57,719
هر ترکیبی از دو عدد نگاه کنید
27
00:00:57,719 –> 00:00:59,100
فرض کنید از اولین
28
00:00:59,100 –> 00:01:01,440
شماره یک شروع می کنیم، بیایید به هر عددی
29
00:01:01,440 –> 00:01:03,629
که با یک ترکیب شده است نگاه کنیم و ببینیم که آیا می
30
00:01:03,629 –> 00:01:06,030
تواند به هدف نه خلاصه شود، بنابراین ابتدا
31
00:01:06,030 –> 00:01:09,930
1 به علاوه 3 یعنی 4 را بررسی می کنیم تا 9 نباشد
32
00:01:09,930 –> 00:01:13,290
سپس 1 به علاوه 4 را بررسی می کنیم. این 5 است سپس 1
33
00:01:13,290 –> 00:01:17,670
به علاوه 5 را بررسی می کنیم که 6 است 1 به علاوه 7 است 8 و 1 به علاوه
34
00:01:17,670 –> 00:01:20,850
10 است 11 بنابراین اکنون به
35
00:01:20,850 –> 00:01:23,700
نقطه ای رسیده ایم که در 1 به علاوه 10 اما
36
00:01:23,700 –> 00:01:25,799
نکته جالب در مورد این این است
37
00:01:25,799 –> 00:01:28,350
که این اولین ترکیب است که بزرگتر
38
00:01:28,350 –> 00:01:31,470
از هدف ما 9 است، بنابراین باید به
39
00:01:31,470 –> 00:01:33,990
عنصر بعدی نگاه کنیم زیرا می
40
00:01:33,990 –> 00:01:36,960
دانیم که آرایه از قبل مرتب شده است،
41
00:01:36,960 –> 00:01:39,479
هیچ عددی بعد از 10 وجود ندارد
42
00:01:39,479 –> 00:01:42,119
که به 1 اضافه می شود که
43
00:01:42,119 –> 00:01:45,540
احتمالاً ممکن است مقداری به هدف 9 باشد، بنابراین از آنجایی که 1
44
00:01:45,540 –> 00:01:47,490
به علاوه 10 است. در حال حاضر بزرگتر از
45
00:01:47,490 –> 00:01:49,229
هدف، ما مجبور نیستیم به
46
00:01:49,229 –> 00:01:50,939
بقیه آرایه نگاه کنیم، زیرا
47
00:01:50,939 –> 00:01:53,729
هیچ عددی وجود ندارد که احتمالاً بعد از
48
00:01:53,729 –> 00:01:56,040
اضافه شدن 10 به 1 باشد که همیشه
49
00:01:56,040 –> 00:01:57,960
هدف باشد، هر عدد بزرگتر
50
00:01:57,960 –> 00:01:59,430
از هدف خواهد بود، بنابراین ما نمیکنیم. دیگر نباید
51
00:01:59,430 –> 00:02:01,380
11 را در نظر بگیریم،
52
00:02:01,380 –> 00:02:03,329
بنابراین اساساً آن را از آن حذف می کنیم
53
00:02:03,329 –> 00:02:05,549
در نظر گرفتن از آرایه ما، بنابراین ما
54
00:02:05,549 –> 00:02:07,860
دو عددی را که حاصل جمع
55
00:02:07,860 –> 00:02:09,929
هدف هستند، پیدا نکردیم، بنابراین اکنون بیایید سعی
56
00:02:09,929 –> 00:02:11,970
کنیم ترکیبی با 3 وجود داشته باشد که احتمالاً می تواند
57
00:02:11,970 –> 00:02:13,739
2
58
00:02:13,739 –> 00:02:17,909
باشد، بنابراین از 4 شروع می کنیم بنابراین 3 به علاوه 4 می شود 7 3 به علاوه
59
00:02:17,909 –> 00:02:22,769
5 می شود 8 3 به علاوه 7 10 است بنابراین این
60
00:02:22,769 –> 00:02:26,969
اولین ترکیب 3 به علاوه 7 است که
61
00:02:26,969 –> 00:02:30,840
10 بزرگتر از هدف 9 است بنابراین ما مجبور نیستیم
62
00:02:30,840 –> 00:02:32,939
به هر عددی که
63
00:02:32,939 –> 00:02:35,549
بعد از 7 می آید نگاه کنیم زیرا می دانیم که
64
00:02:35,549 –> 00:02:37,980
هرگز با هدف برابر نخواهد شد بنابراین می توانیم
65
00:02:37,980 –> 00:02:40,500
اساساً بگوییم خوب 10 از در
66
00:02:40,500 –> 00:02:42,540
نظر گرفتن حذف شده است، ما حتی مجبور نیستیم به آن
67
00:02:42,540 –> 00:02:44,790
نگاه کنیم، بنابراین
68
00:02:44,790 –> 00:02:47,219
نتوانستیم ترکیبی با 3 پیدا کنیم که بتواند به هدف 9 برسد، بنابراین
69
00:02:47,219 –> 00:02:49,500
اکنون بیایید عدد بعدی را برای
70
00:02:49,500 –> 00:02:53,159
اولین عدد بعد از 4 بررسی کنیم که 5 است. در این مورد 4
71
00:02:53,159 –> 00:02:56,819
به علاوه 5 دقیقاً هدف 9 ما است، بنابراین
72
00:02:56,819 –> 00:02:59,040
ما راه حل را پیدا کردیم، البته از آنجایی که
73
00:02:59,040 –> 00:03:00,810
راه حل را پیدا کردیم، لازم
74
00:03:00,810 –> 00:03:02,939
نیست هیچ عنصری را که بعد از آن می آید در نظر بگیریم،
75
00:03:02,939 –> 00:03:05,310
بنابراین در این مورد 7 از در
76
00:03:05,310 –> 00:03:07,139
نظر گرفتن حذف می شود و می توانیم خود را برگردانیم.
77
00:03:07,139 –> 00:03:10,409
حل کنید و به یاد داشته باشید که این شاخص
78
00:03:10,409 –> 00:03:13,199
ها بر اساس 1 هستند بنابراین اولین شاخص 1 است
79
00:03:13,199 –> 00:03:16,530
شاخص دوم 2 3 و 4 است، بنابراین
80
00:03:16,530 –> 00:03:17,729
شاخص هایی که قرار است
81
00:03:17,729 –> 00:03:24,030
برگردانیم، 3 و 4 هستند، بنابراین از آنجایی که این یک
82
00:03:24,030 –> 00:03:25,530
راه حل brute force است و ما باید
83
00:03:25,530 –> 00:03:27,509
در کل آرایه که طول
84
00:03:27,509 –> 00:03:30,060
N است، تکرار کنیم. به طور بالقوه این کار را
85
00:03:30,060 –> 00:03:32,430
در بدترین حالت n بار برای هر
86
00:03:32,430 –> 00:03:34,590
عدد در آرایه انجام خواهیم داد، پس این بدان معناست
87
00:03:34,590 –> 00:03:37,739
که بدترین حالت پیچیدگی زمانی ما Big O
88
00:03:37,739 –> 00:03:41,340
از مجذور N است، بنابراین خیلی کارآمد
89
00:03:41,340 –> 00:03:43,709
نیست، اما آیا می توانیم از این واقعیت استفاده کنیم که این آرایه
90
00:03:43,709 –> 00:03:45,900
به ترتیب ما مرتب شده است. مزیت بیایید
91
00:03:45,900 –> 00:03:47,609
به تصویری که به تازگی ترسیم کردیم نگاه کنیم، ابتدا
92
00:03:47,609 –> 00:03:50,400
11 را از در نظر گرفتن در
93
00:03:50,400 –> 00:03:53,489
آرایه حذف کردیم، سپس 10 را حذف کردیم، سپس
94
00:03:53,489 –> 00:03:56,969
7 را حذف کردیم، بنابراین اساساً
95
00:03:56,969 –> 00:03:59,579
عناصر را از انتهای
96
00:03:59,579 –> 00:04:02,939
آرایه به ترتیب معکوس حذف