题目：454. 四数相加 II
思路：
首先，因为下标不同，因此相同的序列可能会出现很多次。
A + B + C + D = 0，那么当知道保存了A+B的和之后，就看有没有A + B = 0 - C - D了。
代码：
func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
res := 0 // 记录个数
maps := make(map[int]int, 0)
for _, v1 := range nums1 { // 把A和B的和全都放在map中
for _, v2 := range nums2 {
maps[v1 + v2]++ // 要记录次数
}
}
for _, v3 := range nums3 { // 计算C和D的和 看看map里有没有-(v3+v4)
for _, v4 := range nums4 {
res += maps[-v3-v4] // 有几个加几次
}
}
return res
}
参考：
题目：383. 赎金信
思路：
这个和昨天的异构词是一样的思路，唯一不同的地方是异构词是每个字母的个数都一样，这道题是可以少用但不能多用。
代码：
func canConstruct(ransomNote string, magazine string) bool {
t := [26]int{} // 存26个字母
for _, v := range magazine {
t[v-'a'] ++ // 每个字母出现次数
}
for _, v := range ransomNote {
ch := v - 'a'
if t[ch] != 0 {
t[ch]-- // 只能用一次
continue
}
return false // 不够用了
}
return true
}
参考：
题目：15. 三数之和
思路：
这道题用哈希最大的一个问题是需要去重，这里用双指针做。
首先固定一个位置即i，剩下两个指针为j和k起始位置分别是i+1以及len-1，在计算和的时候，因为i是不变的，只有j和k变化：
- 当sum大于0时，那么值就需要缩小，因此右指针向左，并且[j,k)中的所有指向的元素加上k指向的元素和都是大于sum的，因此后续无需再考虑k的位置
- 当sum小于0时，那么值就需要增大，因此左指针向右，并且(j,k]中的所有指向的元素加上j指向的元素和都是小于sum的，因此后续无需再考虑k的位置
说明什么，说明这是一个贪心，你只需要看当前是大是小来移动指针即可。注意一点，在范围之外的元素是已经操作完了的，不用担心。分治。
一个剪枝：
- 当
nums[i]>0时，nums[j]和nums[k]必然都是大于0，和一定大于0，后续也是如此，所以直接break掉
三个元素都要写一个去重，如果和上一个元素一样直接continue。
代码：
双指针解决
func threeSum(nums []int) [][]int {
lens := len(nums)
res := [][]int{} // 结果
if lens < 3 { // 不足三个元素直接返回空
return [][]int{}
}
sort.Ints(nums) // 要先排序一下
for i := 0 ; i < lens-2; i++ { // 注意是 i < lens - 2
if nums[i] > 0 { // 剪枝1
break
}
if i > 0 && nums[i-1] == nums[i] { // 去重i
continue
}
j, k := i + 1, lens - 1 // 两个指针
for j < k {
n1, n2, n3 := nums[i], nums[j], nums[k]
sum := n1 + n2 + n3
if sum < 0 { // 左指针向右
j++
}else if sum > 0 { // 右指针向左
k--
}else if sum == 0{
res = append(res, []int{n1,n2,n3})
for j < k && nums[j] == n2 { // 去重j
j++
}
for j < k && nums[k] == n3 { // 去重k
k--
}
}
}
}
return res
}
参考：
题目：18. 四数之和
思路：
上面是三维变二维，这个是四维变三维，思路都是一样的。
抓住一个重点——去重，每一个元素都需要进行去重操作。因为这个题不是和为0而是固定的target因此不能简单的通过第一个元素去剪枝，而是四个元素同时使用才能剪枝。
代码：
func fourSum(nums []int, target int) [][]int {
lens := len(nums)
res := [][]int{}
if lens < 4 {
return [][]int{}
}
sort.Ints(nums)
for i := 0; i < lens - 3; i++ {
if i > 0 && nums[i] == nums[i-1] { // 去重i
continue
}
for j := i + 1; j < lens - 2; j++ {
if j > i + 1 && nums[j] == nums[j-1] { // 去重j
continue
}
l, r := j + 1, lens - 1
for l < r {
n1, n2, n3, n4 := nums[i], nums[j], nums[l], nums[r]
sum := n1 + n2 + n3 + n4
if sum < target {
l ++
}
if sum > target {
r --
}
if sum == target {
res = append(res, []int{n1,n2,n3,n4})
for l < r && nums[l] == n3 { // 去重l
l ++
}
for l < r && nums[r] == n4 { // 去重r
r --
}
}
}
}
}
return res
}