题目：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变化：

1. 当sum大于0时，那么值就需要缩小，因此右指针向左，并且[j,k)中的所有指向的元素加上k指向的元素和都是大于sum的，因此后续无需再考虑k的位置
2. 当sum小于0时，那么值就需要增大，因此左指针向右，并且(j,k]中的所有指向的元素加上j指向的元素和都是小于sum的，因此后续无需再考虑k的位置

说明什么，说明这是一个贪心，你只需要看当前是大是小来移动指针即可。注意一点，在范围之外的元素是已经操作完了的，不用担心。分治。

一个剪枝：

1. 当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
}

参考：

代码随想录