[Go] Array and String - Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

 

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

 

Constraints:

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

 

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

 

My code

func minSubArrayLen(target int, nums []int) int {
	lp, rp := -1, -1
	sum := 0
	size := math.MaxInt

	for rp < len(nums) || lp < len(nums) {
		if sum < target && rp != len(nums)-1 {
			rp++
			sum += nums[rp]
		} else if sum >= target && lp < rp {
			lp++
			sum -= nums[lp]
		} else if sum < target && rp == len(nums) {
			break
		} else {
			break
		}
		if sum >= target {
			if size > rp-lp {
				size = rp - lp
			}
		}

	}
	if size == math.MaxInt {
		return 0
	}
	return size
}

https://go.dev/play/p/jciisoPehWP

• I initialize lp and rp to -1 due to increment.
• For loop will run until lp and rp exceed length of nums.
• If condition will check sum is less or greater than target.
• when if condition which checks sum is less than target has also rp length check.
• because it will be used when sum needs to be added.
• lf rp is less than length, rp can increase, if rp is same with length, it will break.
• Another if condition will check sum is greater than target for decease.
• lp must be less than rp.
• Next if condition checks sum is same or greater than target.
• if so, size will be calculated and check numbers.
• This code wants shortest subarray length to reach target.
• last if condition checks size has initial value.
• when it has, 0 will be returned.

 

sample 0 ms submission

func minSubArrayLen(s int, nums []int) int {
	sum := 0
    left := 0
    res := math.MaxInt32
    for right := 0; right < len(nums); right ++ {
        sum += nums[right]
        for sum >= s {
            res = min(res, right - left + 1)
            sum -= nums[left]
            left++
        }
    }
    if res == math.MaxInt32 {
        return 0
    } else {
        return res
    }
}

func min(a, b int) int {
	if a < b {
		return a
	}

	return b
}

• This code looks more readible and simple then my code.
• sum and left and res are initialzed to 0, 0 and maxInt respectively.
• Next for loop initialize right and it will run until it reaches to length of nums.
• nums[right] will be added to sum.
• For loop in this will run when sum is bigger than s(target value)
• min function which was declared will check minimum length of subarray and return shortest one.
• and left value will be deducted from sum.
• left will increase.

sample 1 ms submission

func minSubArrayLen(target int, nums []int) int {
    i := 0
    l := len(nums)
    sum := 0
    result := l + 1
    for j := 0; j < l; j ++ {
        sum += nums[j]
        for sum >= target{
            curLength :=  j - i + 1
            if curLength < result{
                result = curLength
            }
            
            sum -= nums[i]
            i ++
        }
    }
    
    if result == l + 1{
        return 0
    }
    
    return result
}

sample 2 ms submission

func min(a, b int) int {
    if a < b {
        return a
    }
    
    return b
}


const maxV = 100000


func minSubArrayLen(target int, nums []int) int {
    res := maxV 
    l := 0
    sum := 0
    
    for r, n := range nums {
        sum += n
        
        for sum >= target {
            res = min(r - l + 1, res)
            
            sum -= nums[l]
            l++
        }
    }
    
    if res == maxV {
        return 0
    }
    
    return res
}

sample 3 ms submission

func minSubArrayLen(target int, nums []int) int {
    minLength := 1 << 32
    
    start := 0
    end := 0
    tally := 0
    currLen := 0
    
    for _, v := range nums {
        end += 1
        currLen += 1
        tally += v
       
        for tally >= target {
            if currLen < minLength {
                minLength = currLen
            }
            tally -= nums[start]
            currLen -= 1
            start += 1
        }
    }
    
    if minLength == 1 << 32 {
        return 0
    }
    
    return minLength
}

sample 4 ms submission & sample 3700 KB submission

func minSubArrayLen(target int, nums []int) int {
    sum, start, subLength := 0, 0, 0
    res := len(nums) + 1
    for end := 0; end < len(nums); end++ {
        sum += nums[end]
        for sum >= target {
            subLength = end - start + 1
            if subLength < res {
                res = subLength
            }
            sum -= nums[start]
            start++
        }
    }
    
    if res == len(nums) + 1 {
        return 0
    }else {
        return res
    }
}

sample 5 ms submission

func minSubArrayLen(target int, nums []int) int {
    minLength := len(nums) + 1
    left, right := 0, 0
    sum := nums[0]
    for left <= right && right < len(nums) {
        if sum >= target {
            length := right - left + 1
            if length < minLength {
                minLength = length
            }
            
            sum -= nums[left]
            left++
        } else {
            right++
            if right < len(nums) {
                sum += nums[right]
            }
        }
    }
    if minLength > len(nums) {
        minLength = 0
    }
    return minLength
}

sample 6 ms submission

func minSubArrayLen(target int, nums []int) int {
    i, j, sum := 0, 0, 0
    min := len(nums) + 1
    for ;j < len(nums); j++ {
        sum += nums[j]
        for sum >= target {
            if min > j - i + 1{
                min = j - i + 1
            }
            sum -= nums[i]
            i++
        }
    }
    if min == len(nums) + 1 {
        return 0
    }
    return min
}

sample 7 ms submission

func minSubArrayLen(target int, nums []int) int {
    
    minLen := len(nums) + 1
    sum := 0
    
    for start, end := 0, 0; end < len(nums); end++ {
        
        sum += nums[end]
        
        for ;start <= end && sum >= target ; start++ {
            if (end - start + 1 <= minLen) {
                minLen = end - start + 1
            }
            sum -= nums[start]
        }
    }
    
    if (minLen == len(nums) + 1)  {
        return 0
    }
    return minLen

}

sample 3800 KB submission

func minSubArrayLen(target int, nums []int) int {
    for k:=1; k<=len(nums); k++{
        wStart := 0
        wSum := 0
        for wEnd:=0; wEnd<len(nums); wEnd++{
            wSum = wSum + nums[wEnd]
            if wEnd >= k-1 {
                if wSum >= target{
                        return k
                }
                wSum = wSum - nums[wStart];
                wStart++;
            }
        }
    }
    return 0
}