Incorrect Absolute Difference Usage
创建于:2025年1月24日
创建于:2025年1月24日
Look at this solution for the Leetcode problem 413 Arithmetic Slices and explain why it's incorrect:
func numberOfArithmeticSlices(nums []int) int {
res:=0
if len(nums) < 3 {
return 0
}
start:=0
diff:=math.Abs(float64(nums[0]-nums[1]))
for i,j:=1,0;i<=len(nums);i,j=i+1,j+1 {
if i==len(nums) {
n:=i-start-2
res+= n*(n+1)/2
break
}
if math.Abs(float64(nums[i]-nums[j])) != diff {
if i<len(nums)-1 {
diff=math.Abs(float64(nums[i]-nums[i+1]))
}
n:=i-start-2
res+= n*(n+1)/2
start=i
}
}
return res
}
First, recall what the problem (Leetcode #413) is asking for:
We need to find the number of arithmetic subarrays (subarrays of length ≥ 3) in the given array. An arithmetic subarray is one where the difference between consecutive elements is the same (including its sign), for example: has consecutive differences +2, +2, +2.
Now, let’s look at the provided solution and see what goes wrong:
gofunc numberOfArithmeticSlices(nums []int) int { res := 0 if len(nums) < 3 { return 0 } start := 0 diff := math.Abs(float64(nums[0] - nums[1])) for i, j := 1, 0; i <= len(nums); i, j = i+1, j+1 { if i == len(nums) { n := i - start - 2 res += n * (n + 1) / 2 break } if math.Abs(float64(nums[i] - nums[j])) != diff { if i < len(nums)-1 { diff = math.Abs(float64(nums[i] - nums[i+1])) } n := i - start - 2 res += n * (n + 1) / 2 start = i } } return res }
The primary mistake is doing:
godiff := math.Abs(float64(nums[0] - nums[1]))
and then checking:
goif math.Abs(float64(nums[i] - nums[j])) != diff { // ... }
Leetcode #413 does not define an arithmetic subarray based on the absolute value of the difference. Instead, the difference including its sign must remain constant for the subarray to be arithmetic. For example:
diff = 2
.diff = -2
.By using the absolute value, this code would incorrectly conclude that, for instance, is an arithmetic slice if all it looks at is |3-5| = 2
and |5-1| = 4
—these are not the same, but we never should use absolute differences in the first place. And if they accidentally matched in absolute value, that would also be incorrect. The sign does matter for valid arithmetic subarrays.
The correct approach is to keep track of the signed difference:
godiff := nums[1] - nums[0]
Then, while iterating, check whether the next consecutive difference is exactly the same nums[i] - nums[i-1] == diff
.
The usual approach is:
A common clean approach (in pseudo-code or Go) is:
gocount := 0 // how many arithmetic slices so far currentLen := 2 // length of the current arithmetic run diff := nums[1] - nums[0] for i from 2 to len(nums)-1: if (nums[i] - nums[i-1]) == diff: currentLen++ else: // currentLen means you have currentLen >= 2 consecutive arithmetic // subarray of length `currentLen` yields (currentLen - 2)*(currentLen - 1)/2 slices if currentLen >= 2 { count += (currentLen - 2)*(currentLen - 1)/2 } // reset diff = nums[i] - nums[i-1] currentLen = 2 // loop ends // need to add slices from the last run if currentLen >= 3 if currentLen >= 3 { count += (currentLen - 2)*(currentLen - 1)/2 } return count
This way:
math.Abs
), whereas arithmetic slices require matching signed differences.Implement the solution you proposed in Golang
Below is a clean and concise Go implementation that solves Leetcode #413 (Arithmetic Slices) correctly by tracking the signed difference and summing up the counts of arithmetic runs:
gofunc numberOfArithmeticSlices(nums []int) int { n := len(nums) if n < 3 { return 0 } // 'count' will store the total number of arithmetic sub-slices count := 0 // 'currentLen' will track the length of the current arithmetic run currentLen := 2 // Initialize the difference using the first two elements diff := nums[1] - nums[0] for i := 2; i < n; i++ { currentDiff := nums[i] - nums[i-1] if currentDiff == diff { // Continue the arithmetic run currentLen++ } else { // We ended the previous run, so count how many arithmetic // sub-slices it contributed: the formula is (currentLen-2)*(currentLen-1)/2 if currentLen >= 3 { count += (currentLen - 2) * (currentLen - 1) / 2 } // Reset for the new run diff = currentDiff currentLen = 2 } } // If we ended with a run of length >= 3, we need to count its sub-slices as well if currentLen >= 3 { count += (currentLen - 2) * (currentLen - 1) / 2 } return count }
diff := nums[1] - nums[0]
.currentLen++
.currentLen >= 3
.This ensures we only treat arithmetic slices where the signed difference is identical (e.g., +2 vs. -2 are distinct differences) and correctly sum all arithmetic sub-slices of length ≥ 3.