Advertisement
Alexxik

Untitled

Sep 16th, 2023 (edited)
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Swift 0.85 KB | None | 0 0
  1. // MARK: - Найти ЛЮБОЙ подотрезок суммой X
  2.  
  3. func subarraySumXAny(_ nums: [Int], _ x: Int) -> [Int] {
  4.  
  5.     // храним префикс и где он заканчивается
  6.     var prefix = [0:-1]
  7.     var sum = 0
  8.    
  9.     for r in 0..<nums.count {
  10.        
  11.         sum += nums[r]
  12.        
  13.         var prefixForDelete = sum - x
  14.        
  15.         if prefix[prefixForDelete] != nil {
  16.             // тут прибавляем 1, чтобы считать не конец префикса, а начало подмассива без префикса
  17.             let start = prefix[prefixForDelete]! + 1
  18.             return Array(nums[start...r])
  19.         }
  20.        
  21.         // !!! в словарь добавляется сумма
  22.         prefix[sum] = r
  23.     }
  24.     return [-1]
  25. }
  26.  
  27. subarraySumXAny([1,2,3,4,5,0], 12)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement