Swift solution - Prefix Sum, Math


  • 0
    class Solution {
        func checkSubarraySum(_ nums: [Int], _ k: Int) -> Bool {
            var map = [0: -1]
            var runningSum = 0
            
            for i in 0..<nums.count {
                runningSum += nums[i]
                if k != 0 {
                    runningSum %= k
                }
                if let prev = map[runningSum] {
                    if i - prev > 1 {
                        return true
                    }
                } else {
                    map[runningSum] = i
                }
            }
            
            return false
        }
        
        func checkSubarraySum_PrefixSum(_ nums: [Int], _ k: Int) -> Bool {
            if nums.count == 0 {
                return false
            }
            
            let n = nums.count
            var preSum = [Int](repeatElement(0, count: n + 1))
            
            for i in 1...n {
                preSum[i] = preSum[i - 1] + nums[i - 1]
            }
            for i in 0..<(n - 1) {
                for j in (i + 2)...n {
                    if k == 0 {
                        if preSum[j] - preSum[i] == 0 {
                            return true
                        }
                    } else if (preSum[j] - preSum[i]) % k == 0 {
                        return true
                    }
                }
            }
            
            return false
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.