Advertisement
Alexxik

Untitled

Sep 11th, 2023 (edited)
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Swift 1.28 KB | None | 0 0
  1. // MARK: - 560. Subarray Sum Equals K
  2. // Используем словарь, где ключ - префиксная сумма, а значение кол-во раз сколько получилась префиксаня сумма
  3.  
  4.  
  5. func subarraySum(_ nums: [Int], _ k: Int) -> Int {
  6.    
  7.     // Базовый случай префиксной суммы, когда пустой префиксный подмассив и сам подмассив суммой k
  8.     var prefixSumDict: [Int:Int] = [0:1]
  9.    
  10.     var sum = 0
  11.     var result = 0
  12.    
  13.     for num in nums {
  14.         sum += num
  15.        
  16.         // если мы можем удалить из sum префикс dif и получить k, то это то что нужно и по словарю смотрим сколько раз это можем сделать
  17.         // k = sum - dif
  18.  
  19.         var dif = sum - k
  20.        
  21.         // Проверяем есть ли этот префикс в словаре (как бы проаеряем можем ли мы удалить из массива dif и получить k)
  22.         if prefixSumDict[dif] != nil {
  23.             result += prefixSumDict[dif]!
  24.         }
  25.        
  26.         prefixSumDict[sum, default: 0] += 1
  27.     }
  28.     return result
  29. }
  30. subarraySum([1,2,3], 3)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement