1. Two Sum

هفته اول شماره ۱

مسئله ۱- Two Sum:

فرض کنید nums آرایه‌ای از اعداد صحیح و target یک عدد صحیح باشد، این تابع indexهای دو عدد را در آرایه nums برمی‌گرداند که وقتی مقدار آن‌ها با هم جمع شوند برابر با مقدار عددی target شوند.

می‌توانید فرض کنید که برای هر ورودی دقیقا یک جواب وجود دارد و از یک عدد دو بار استفاده نمی‌شود. همینطور ترتیب بازگرداندن جواب‌ها اهمیت ندارد.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

قیدها:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• فقط یک جواب معتبر وجود دارد

نکته: آیا می‌توانید الگوریتمی ارائه دهید که پیچیدگی زمانی آن کمتر از O(n2) باشد؟

راه‌حل : جدول Hash

می‌توانیم از یک جدول Hash به نام m برای ذخیره مقادیر آرایه و زیرنویس‌های آن‌ها استفاده کنیم.

هنگام پیمایش آرایه nums، اگر target - nums[i] را در جدول Hash پیدا کردیم، به این معنی است که مقدار هدف یافت شده‌است و شاخص‌های target - nums[i] و i برگردانده می‌شوند.

پیچیدگی زمانی این راه‌حل O(n) و پیچیدگی فضایی آن نیز  O(n) است. که در آن n طول آرایه nums می‌باشد.

راه حل تصویری:

کد:

func twoSum(nums []int, target int) []int {
 m := map[int]int{}
 for i := 0; ; i++ {
  x := nums[i]
  y := target - x
  if j, ok := m[y]; ok {
   return []int{j, i}
  }
  m[x] = i
 }
}