S2
S2 copied to clipboard
halfrost
0015.3 Sum | LeetCode Cookbook
看了半天上面大部分是考虑重复数字的，只有下面一点才是普通情况的计算，看来题目稍微改动一点，复杂度大大增加
c := 0 - uniqNums[i] - uniqNums[j]
if c > uniqNums[j] && counter[c] > 0 {
res = append(res, []int{uniqNums[i], uniqNums[j], c})
}
看了半天上面大部分是考虑重复数字的，只有下面一点才是普通情况的计算，看来题目稍微改动一点，复杂度大大增加
c := 0 - uniqNums[i] - uniqNums[j] if c > uniqNums[j] && counter[c] > 0 { res = append(res, []int{uniqNums[i], uniqNums[j], c}) }
@fakeYanss 是的~你可以顺着 Two-sum 开始做，一直做到 Four-sum，会有这种感受。four-sum 感觉没有这一题难。
if index > 1 && nums[index] == nums[index-1] { start = index - 1 } 第一个解法 里为什么是start = index - 1，而不是index--呢？
@wang-dahua 外层的 index 遍历的是大循环，在这个循环里面 start 和 end 是滑动窗口的 2 个指针。在窗口滑动过程中，不能改变外层 index 的值。如果改变了 index，就导致当前滑动窗口基于的初始状态发生变化了，答案就不对了。
我很愚蠢，下面这一步不是很理解：
// 这一步还不是很了解
if index > 1 && nums[index] == nums[index-1] {
start = index - 1
}
@guowei-gong 我很愚蠢，下面这一步不是很理解：
// 这一步还不是很了解 if index > 1 && nums[index] == nums[index-1] { start = index - 1 }
这里是结合下面 for start < index && end > index 循环发挥作用的。此时 index 和 index -1 的元素相等，需要直接跳过，就把 start 重置成 index -1，这样在下面的循环里就会直接命中 start > 0 && nums[start] == nums[start-1] 这个条件跳出循环了
我很愚蠢，下面这一步不是很理解：
// 这一步还不是很了解 if index > 1 && nums[index] == nums[index-1] { start = index - 1 }
@guowei-gong 你不愚蠢。大家都是这样过来的。很抱歉回复你的消息回复慢了。你这个问题的答案，在你下面一楼那个同学回复了。
解法一会不会有点繁琐，有几处看不太懂。换成这样会不会直观点？（速度内存结果貌似都差不多，刷题新人若有误见谅）
func threeSum(nums []int) [][]int {
//nums排序
sort.Ints(nums)
ans := make([][]int, 0)
for i, v := range nums {
//若是重复数字，跳过此次过程判断下一个数字
if i > 0 && v == nums[i-1] {
continue
}
//t_sum是剩下两个数字和的值
t_sum := 0 - v
//左右指针开始地点
left := i + 1
right := len(nums) - 1
for left < right {
if nums[left]+nums[right] < t_sum {
left++
} else if nums[left]+nums[right] > t_sum {
right--
} else {
//找到一组，装进答案继续，移动左指针往右一次
ans = append(ans, []int{v, nums[left], nums[right]})
left++
//再次循环判断移动左指针来跳过重复数字的地方；不会增加复杂度因为父循环同样检查left<right
for nums[left] == nums[left-1] && left < right {
left++
}
}
}
}
return ans
}
