Leetcode 001 Two Sum

Soru

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Örnek 1

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

Örnek 2

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

Örnek 3

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

Çözüm

• Burada bize bir liste ve bir sayı veriliyor.Listedeki 2 sayının toplamı bu sayıya(target) eşitmiş.Bizden bu 2 sayının indexleri isteniyor.
• Basit bir çözüm, her sayı için diğer tüm sayıları kontrol ederek doğru çifti bulmaktır. Ancak bu yaklaşımın zaman karmaşıklığı O(n^2)‘dir, bu da büyük veri setleri için uygun olmayabilir.
• Ama sorunun devamında bizden T.C. o(n) olması istenmektedir.
• Daha etkili bir çözüm yöntemi, bir hash table kullanmaktır. Hash table (veya Python’da dict), işlemleri ortalama O(1) zamanda yapmanıza olanak tanır, bu da bu problem için çok uygundur.
• Bu çözümde, dizideki her eleman için, hedef sayıdan o elemanı çıkardığınızda geriye kalan değerin daha önce dizide karşılaşıp karşılaşmadığını kontrol edersiniz. Eğer karşılaşmışsanız, bu iki sayının toplamı hedef sayıya eşit olduğu anlamına gelir ve bu sayıların indekslerini döndürürsünüz. Bu yöntem, her elemanı yalnızca bir kez kontrol ettiği ve hash table ile hızlı bir şekilde geri kalan değeri sorguladığı için O(n) zaman karmaşıklığına sahiptir.

Code

   def twoSum(self, nums, target):
      required = {}
      for i in range(len(nums)):
         if target - nums[i] in required:
            return [required[target - nums[i]],i]
         else:
            required[nums[i]]=i

Complexity

• Zaman Karmaşıklığı (Time Complexity): Bu yöntemde, dizinin her elemanı sırasıyla incelenir. Her eleman için, hedef sayıdan çıkarıldığında kalan değer hash table’da zaten var mı diye kontrol edilir. Bu kontrol işlemi hash table kullanıldığı için ortalama O(1) zaman alır. Tüm dizi bir kez döngüden geçirildiğinden, bu çözümün zaman karmaşıklığı O(n) olur, burada n dizinin uzunluğudur. </

• Alan Karmaşıklığı (Space Complexity): Bu çözümde, her bir dizi elemanını ve onun indeksini bir hash table’da saklamamız gerekiyor. En kötü durumda, yani çözümü bulana kadar tüm elemanları hash table’a eklememiz gerektiğinde, hash table’ın boyutu n elemana kadar büyüyebilir. Bu nedenle, bu çözümün alan karmaşıklığı O(n) olur.